Low-Earth-Orbit (LEO) satellite constellations provide Internet connectivity across the globe, but their network design poses significant challenges due to the large number of satellites and their fast movement. Named Data Networking (NDN) can bring many benefits to LEO satellite networks such as data-centric security, scalable content distribution, and intelligent data plane. A key enabler to these benefits is NDN's stateful forwarding, which unfortunately can be disrupted by the frequent handovers between the satellites and the ground terminals. In this paper, we investigate the impacts of these handovers on NDN's packet delivery and propose effective mitigation mechanisms. Using a newly developed packet-level simulator and in-depth analysis of packet forwarding behavior during handovers, we show that consumer handovers and producer handovers both lead to temporary packet losses but for different causes. To mitigate these problems, we design a new Interest retransmission strategy to handle consumer handovers, and a new forwarding strategy to handle producer handovers. Our evaluation shows that these solutions are effective in reducing packet losses and delivery time. This work sheds insights on how NDN can work in the presence of frequent satellite-ground handovers to enable data-centric communication in this new network environment.

Packet encapsulation is a general network technique that provides an essential building block for constructing secure networks. While extensively used in IP networks over the last few decades, secure packet encapsulation remains largely unexplored in the context of Named Data Networking (NDN) networks. NDN represents a radical departure from traditional endpoint-oriented networking by making secured data the centerpiece of communication. This new data-centric design brings both advantages and new challenges for the development of secure packet encapsulation that can preserve essential properties of an NDN network, including in-network data caching and builtin multicast data delivery. In this paper, we first identify the major differences between encapsulation solution designs in IP and NDN, highlighting the ensuing challenges, both inherent and practical. We then present a novel design to achieve secure NDN data packet encapsulation, and showcase an implementation suite that enables efficient fetching of securely encapsulated data.11The views, opinions and/or findings expressed are those of the authors and should not be interpreted as representing the official views or policies of the Department of Defense or the U.S. Government. Distribution Statement “A” (Approved for Public Release, Distribution Unlimited)

Named-Data Networking (NDN) is a novel network that secures network communication by fetching semantically named and secured data. All data packets in NDN are signed by producers and verified by data consumers. Therefore, it is vital to have producers' certificates available all the time. In this paper, we describe the design of CLedger, a secure distributed certificate ledger, to ensure certificate availability in NDN. CLedger logs certificate records in an immutable Directed Acyclic Graph (DAG) structure and replicates the DAG among a set of distributed loggers. We implemented CLedger using NDN's pub/sub API, and evaluated our design through an emulated deployment setting. Our initial evaluation results show that CLedger is effective, efficient, and resilient to failures.

Recent years have witnessed the rapid deployment of smart homes; most of them are controlled by remote servers in the cloud. Such designs raise security and privacy concerns for end users. In this article, we describe the design of Sovereign, a home Internet of Things (IoT) system framework that provides end users complete control of their home IoT systems. Sovereign lets home IoT devices and applications communicate via application-named data and secures data directly. This approach enables direct, secure, one-to-one, and one-to-many Device-to-Device communication over wireless broadcast media. Sovereign utilizes semantic names to construct usable security solutions. We implement Sovereign as a publish–subscribe-based development platform together with a prototype home IoT controller. Our preliminary evaluation shows that Sovereign provides a systematic, easy-to-use solution to user-controlled, self-contained smart homes running on existing IoT hardware without imposing noticeable overhead.

In this paper we explore solutions to robust group communication in disadvantaged wireless networks that exhibit low bandwidth, high packet losses, and frequent or even permanent network partitions. More specifically, we propose a group communication protocol based on Named Data Networking (NDN). By design, NDN’s in-network caching and stateful forwarding plane can help improve data delivery robustness in disadvantaged networks, but when content is generated with dynamic rates, an efficient, low-overhead synchronization protocol is needed to inform group members to fetch newly generated content promptly. In this paper, we describe the Prefetch Loss-Insensitive Sync (PLI-Sync) protocol for group communication in highly disadvantaged networks. PLI-Sync combines optimistic content pre-fetching with new content notification via sync, and addresses the challenges of how to distinguish wireless packet losses from mobility-induced disconnections, and between data availability and retrievability. Our evaluations show that leveraging the interplay between optimistic pre-fetching and a low rate sync protocol can significantly reduce communication overhead compared to relying on sync protocols alone, while maintaining low data fetching latency and robust delivery in a variety of wireless conditions and traffic load settings.

Abstract Anonymous credentials are a solid foundation for privacy-preserving Single Sign-On (SSO). They enable unlinkable authentication across domains and allow users to prove their identity without revealing more than necessary. Unfortunately, anonymous credentials schemes remain difficult to use and complex to deploy. They require installation and use of complex software at the user side, suffer from poor performance, and do not support security features that are now common, such as two-factor authentication, secret recovery, or support for multiple devices. In contrast, Open ID Connect (OIDC), the de facto standard for SSO is widely deployed and used despite its lack of concern for users’ privacy. We present EL PASSO, a privacy-preserving SSO system based on anonymous credentials that does not trade security for usability, and can be incrementally deployed at scale alongside Open ID Connect with no significant changes to end-user operations. EL PASSO client-side operations leverage a WebAssembly module that can be downloaded on the fly and cached by users’ browsers, requiring no prior software installation or specific hardware. We develop automated procedures for managing cryptographic material, supporting multi-device support, secret recovery, and privacy-preserving two-factor authentication using only the built-in features of common Web browsers. Our implementation using PS Signatures achieves 39x to 180x lower computational cost than previous anonymous credentials schemes, similar or lower sign-on latency than Open ID Connect and is amenable for use on mobile devices.

This paper introduces DAta-centric Peer-to-peer filE Sharing (DAPES), a data sharing protocol for scenarios with intermittent connectivity and user mobility. DAPES provides a set of semantically meaningful hierarchical naming abstractions that facilitate the exchange of file collections via local connectivity. This enables peers to "make the most" out of the limited connection time with other peers by maximizing the utility of individual transmissions to provide data missing by most connected peers. DAPES runs on top of Named-Data Networking (NDN) and extends NDN's data-centric network layer abstractions to achieve communication over multiple wireless hops through an adaptive hop-by-hop forwarding/suppression mechanism. We have evaluated DAPES through real-world experiments in an outdoor campus setting and extensive simulations. Our results demonstrate that DAPES achieves 50-71% lower overheads and 15-33% lower file sharing delays compared to file sharing solutions that rely on IP-based mobile ad-hoc routing.

Publish-subscribe (pub-sub) has been recognized as a common communication pattern in IoT applications. In this paper we present ndnBMS-PS, a distributed pub-sub communication framework for building management systems (BMS), an important area of IoT, over the Named Data Networking (NDN) architecture. ndnBMS-PS utilizes distributed NDN repositories to store and republish large quantities of BMS data that can be consumed by different applications. It employs a data synchronization mechanism to aggregate multiple data streams published by multiple sensing devices and achieve efficient notification of new data for the consumers. ndnBMS-PS also provides data authentication by utilizing NDN's security building blocks. This design exercise demonstrates that the information-centric architecture enables a simple design for complex IoT systems and provides superior system efficiency and security over TCP/IP-based alternatives.

Disruptive network scenarios with ad hoc, intermittent connectivity and mobility create unique challenges to supporting distributed applications. In this paper, we propose Distributed Dataset Synchronization over disruptive Networks (DDSN), a protocol which provides resilient multi-party communication in adverse communication environments. DDSN is designed to work on top of the Named-Data Networking protocol and utilizes semantically named, and secured, packets to achieve distributed dataset synchronization through an asynchronous communication model. A unique design feature of DDSN is letting individual entities exchange their dataset states directly, instead of using some compressed form of the states. We have implemented a DDSN prototype and evaluated its performance through simulation experimentation under various packet loss rates. Our results show that, compared to an epidemic routing based data dissemination solution, DDSN achieves 33-56% lower data retrieval delays and 40-44% lower overheads, with up to 20% packet losses. When compared to the existing NDN dataset synchronization protocols, DDSN can lower the state and data synchronization delays from one-third to two-third, and lower the protocol overhead by up to one-third, with the performance difference becoming more pronounced as network loss rates go up.

DNS provides a global-scale distributed lookup service to retrieve data of all types for a given name, be it IP addresses, service records, or cryptographic keys. This service has proven essential in today's operational Internet. Our experience with the design and development of Named Data Networking (NDN) suggests the need for a similar always-on lookup service. To fulfill this need we have designed the NDNS (NDN DNS) protocol, and learned several interesting lessons through the process. Although DNS's request-response operations seem closely resembling NDN's Interest-Data packet exchanges, they operate at different layers in the protocol stack. Comparing DNS's implementations over IP protocol stack with NDNS's implementation over NDN reveals several fundamental differences between applications designs for host-centric IP architecture and data-centric NDN architecture.

BitTorrent is a popular application for peer-to-peer file sharing in today's Internet. To achieve robust and efficient data dissemination as an application overlay, BitTorrent implements a data-centric paradigm on top of TCP/IP's point-to-point packet delivery, which requires each peer to obtain network layer connectivity information (e.g., peer IP address, distance to each peer, routing policies) that is exclusively available at the network layer in order to select the best peers for data retrieval. This paper presents the design of nTorrent, which provides BitTorrent-like functions natively in Named Data Networking (NDN). We use simulations to examine how well the NDN's data-centric communication model can natively support such an application. Our work exposes the differences between the IP- based BitTorrent and nTorrent, and the issues and impact of moving IP-based applications to NDN-enabled networks.

Routing in NDN networks must scale in terms of forwarding table size and routing protocol overhead. Hyperbolic routing (HR) presents a potential solution to address the routing scalability problem, because it does not use traditional forwarding tables or exchange routing updates upon changes in network topologies. Although HR has the drawbacks of producing sub-optimal routes or local minima for some destinations, these issues can be mitigated by NDN's intelligent data forwarding plane. However, HR's viability still depends on both the quality of the routes HR provides and the overhead incurred at the forwarding plane due to HR's sub-optimal behavior. We designed a new forwarding strategy called Adaptive Smoothed RTT-based Forwarding (ASF) to mitigate HR's sub-optimal path selection. This paper describes our experimental investigation into the packet delivery delay and overhead under HR as compared with Named-Data Link State Routing (NLSR), which calculates shortest paths. We run emulation experiments using various topologies with different failure scenarios, probing intervals, and maximum number of next hops for a name prefix. Our results show that HR's delay stretch has a median close to 1 and a 95th-percentile around or below 2, which does not grow with the network size. HR's message overhead in dynamic topologies is nearly independent of the network size, while NLSR's overhead grows polynomially at least. These results suggest that HR offers a more scalable routing solution with little impact on the optimality of routing paths.

The World Wide Web has become the most common platform for building applications and delivering content. Yet despite years of research, the web continues to face severe security challenges related to data integrity and confidentiality. Rather than continuing the exploit-and-patch cycle, we propose addressing these challenges at an architectural level, by supplementing the web's existing connection-based and server-based security models with a new approach: content-based security. With this approach, content is directly signed and encrypted at rest, enabling it to be delivered via any path and then validated by the browser. We explore how this new architectural approach can be applied to the web and analyze its security benefits. We then discuss a broad research agenda to realize this vision and the challenges that must be overcome.

Information sharing among a group of friends or colleagues in real life is usually a distributed process: we tell each other interesting or important news without any mandatory assistance or approval from a third party. Surprisingly, this is not what happens when sharing files among a group of friends over the Internet. While the goal of file sharing is to disseminate files among multiple parties, due to the constraints imposed by IP's point-to-point communication model, most of today's file sharing applications, such as Drop box, Google Drive, etc., resort to a centralized design paradigm: a user first uploads files to the server (cloud), and the server (cloud) re-distributes these files to other users, resulting in unnecessary tussles and inefficient data distribution paths. To bring the truly distributed file sharing back into the cyberspace, this paper presents Chrono Share, a distributed file sharing application built on top of the Named Data Networking (NDN) architecture. By walking through Chrono Share design details, we show how file sharing, as well as many other similar applications, can be effectively implemented over NDN in a truly distributed and secure manner.

This paper proposes Navigo, a location based packet forwarding mechanism for vehicular Named Data Networking (NDN). Navigo takes a radically new approach to address the challenges of frequent connectivity disruptions and sudden network changes in a vehicle network. Instead of forwarding packets to a specific moving car, Navigo aims to fetch specific pieces of data from multiple potential carriers of the data. The design provides (1) a mechanism to bind NDN data names to the producers' geographic area(s); (2) an algorithm to guide Interests towards data producers using a specialized shortest path over the road topology; and (3) an adaptive discovery and selection mechanism that can identify the best data source across multiple geographic areas, as well as quickly react to changes in the V2X network.

As more complex security services have been added to today's Internet, it becomes increasingly difficult to quantify their vulnerability to compromise. The concept of "attack surface" has emerged in recent years as a measure of such vulnerabilities, however systematically quantifying the attack surfaces of networked systems remains an open challenge. In this work we propose a methodology to both quantify the attack surface and visually represent semantically different components (or resources) of such systems by identifying their dependencies. To illustrate the efficacy of our methodology, we examine two real Internet standards (the X.509 CA verification system and DANE) as case studies. We believe this work represents a first step towards systemically modeling dependencies of (and interdependencies between) networked systems, and shows the usability benefits from leveraging existing services.

The DNS Security Extensions (DNSSEC) arguably make DNS the first core Internet system to be protected using public key cryptography. The success of DNSSEC not only protects the DNS, but has generated interest in using this secured global database for new services such as those proposed by the IETF DANE working group. However, continued success is only possible if several important operational issues can be addressed. For example, .gov and .arpa have already suffered misconfigurations where DNS continued to function properly, but DNSSEC failed (thus, orphaning their entire subtrees in DNSSEC). Internet-scale verification systems must tolerate this type of chaos, but what kind of verification can one derive for systems with dynamism like this? In this paper, we propose to achieve robust verification with a new theoretical model, called Public Data, which treats operational deployments as Communities of Trust (CoTs) and makes them the verification substrate. Using a realization of the above idea, called Vantages, we quantitatively show that using a reasonable DNSSEC deployment model and a typical choice of a CoT, an adversary would need to be able to have visibility into and perform on-path Man-in-the-Middle (MitM) attacks on arbitrary traffic into and out of up to 90 percent of the all of the Autonomous Systems (ASes) in the Internet before having even a 10 percent chance of spoofing a DNSKEY. Further, our limited deployment of Vantages has outperformed the verifiability of DNSSEC and has properly validated its data up to 99.5 percent of the time.

With the growing realization that current Internet protocols are reaching the limits of their senescence, several on-going research efforts aim to design potential next-generation Internet architectures. Although they vary in maturity and scope, in order to avoid past pitfalls, these efforts seek to treat security and privacy as fundamental requirements. Resilience to Denial-of-Service (DoS) attacks that plague today's Internet is a major issue for any new architecture and deserves full attention. In this paper, we focus on DoS in Named Data Networking (NDN) -- a specific candidate for next-generation Internet architecture designs. By naming data instead of its locations, NDN transforms data into a first-class entity and makes itself an attractive and viable approach to meet the needs for many current and emerging applications. It also incorporates some basic security features that mitigate classes of attacks that are commonly seen today. However, NDN's resilience to DoS attacks has not been analyzed to-date. This paper represents a first step towards assessment and possible mitigation of DoS in NDN. After identifying and analyzing several new types of attacks, it investigates their variations, effects and counter-measures. This paper also sheds some light on the debate about relative virtues of self-certifying, as opposed to human-readable, names in the context of content-centric networking.

Security is an integral part of networked computer systems. The recent Named Data Networking (NDN) project aims to develop a new Internet architecture that communicates data using names rather than locations, the latter of which is what the current IP-based Internet does with IP addresses. One of the first real-world applications using NDN is a lighting control system. We conduct a red team assessment of the current state of the security of this lighting system and its NDN implementation. The system is representative of a more general class of automated controller systems. Our analysis found that due to NDN's use of named data, the system inherently prevents most attacks that IP-based systems are vulnerable to. Although many parts of the system are secure, we discovered some problems with the verification of timestamps and processing of large packets that led to a severe memory leak. The system also lacks a secure key distribution mechanism. While NDN security is on the right track, there are important security design issues NDN must account for.

We were able to put together an excellent technical program for ICNP 2013, thanks to the joint efforts by our authors, TPC members, and technical area leads. We received 251 submissions to the main conference this year, the highest number in ICNP's 21-year history. Each paper received at least three reviews, and the 66 technical program committee members produced 765 paper reviews. The 11 area chairs ensured review quality and consistency between reviewers. The final papers for the main conference were selected during a TPC meeting in July. To accommodate for the larger number of submissions, we decided to shorten paper presentations slightly. Overall, 46 papers were accepted for presentation at the conference, which corresponds to an acceptance rate of 18.3%.

As more and more authority DNS servers turn on DNS security extensions (DNSSEC), it becomes increasingly important to understand whether, and how many, DNS resolvers perform DNSSEC validation. In this paper we present a query-based measurement method, called Check-Repeat, to gauge the presence of DNSSEC validating resolvers. Utilizing the fact that most validating resolver implementations retry DNS queries with a different authority server if they receive a bad DNS response, Check-Repeat can identify validating resolvers by removing the signatures from regular DNS responses and observing whether a resolver retries DNS queries. We tested Check-Repeat in different scenarios and our results showed that Check-Repeat can identify validating resolvers with a low error rate. We also cross-checked our measurement results with DNS query logs from .COM and .NET domains, and confirmed that the resolvers measured in our study can account for more than 60% of DNS queries in the Internet.

3G/4G cellular networks adopt usage-based charging. Mobile users are billed based on the traffic volume when accessing data service. In this work, we assess both this metered accounting architecture and application-specific charging policies by operators from the security perspective. We have identified loopholes in both, and discovered two effective attacks exploiting the loopholes. The "toll-free-data-access-attack" enables the attacker to access any data service for free. The "stealth-spam-attack" incurs any large traffic volume to the victim, while the victim may not be even aware of such spam traffic.Our experiments on two operational 3G networks have confirmed the feasibility and simplicity of such attacks. We also propose defense remedies.

Although there have been a plethora of studies on TCP performance in supporting of various applications, relatively little is known about the interaction between TCP and BGP, which is a specific application running on top of TCP. This paper investigates BGP's slow route propagation by analyzing packet traces collected from a large ISP and Route Views Oregon collector. In particular we focus on the prolonged periods of BGP routing table transfers and examine in detail the interplay between TCP and BGP. In addition to the problems reported in previous literature, this study reveals a number of new TCP transport problems, that collectively induce significant delays. Furthermore, we develop a tool, named T-DAT, that can be deployed together with BGP data collectors to infer various factors behind the observed delay, including BGP's sending and receiving behavior, TCP's parameter settings, TCP's flow and congestion control, and network path limitation. Identifying these delay contributing factors makes an important step for ISPs and router vendors to diagnose and improve the BGP performance.

Although traceroute has the potential to discover AS links that are invisible to existing BGP monitors, it is well known that the common approach for mapping router IP addresses to AS numbers based on BGP routing tables is highly error-prone. We develop a systematic framework to quantify the potential errors of traceroute measurement in AS-level topology inference. In comparing traceroute-derived AS paths with BGP AS paths, we take a novel approach to identifying mismatched path segments and then inferring the causes of these mismatches through a set of tests. Our results show that about 60% of mismatches are due to routers using IP addresses belonging to peering neighbors. This result helps settle a debate in previous works regarding the major cause of errors in traceroute measurement. With the approximate ground truth of the ASes with BGP monitors inside, we identify the inaccuracy of publicly available traceroute-derived topology datasets and find that between 8% and 42% of AS adjacencies on the monitored ASes are false. With a new method to characterize AS links, we show that the derived (false) links between Tier-1/large ISPs and their customers' customers appear more frequently than real links do.

The DNS Security Extensions (DNSSEC) are among the first attempts to deploy cryptographic protections in an Internet-scale operational system. DNSSEC applies well-established public key cryptography to ensure data integrity and origin authenticity in the DNS system. While the cryptographic design of DNSSEC is sound and seemingly simple, its development has taken the IETF over a decade and several protocol revisions, and even today its deployment is still in the early stage of rolling out. In this paper, we provide the first systematic examination of the design, deployment, and operational challenges encountered by DNSSEC over the years. Our study reveals a fundamental gap between cryptographic designs and operational Internet systems. To be deployed in the global Internet, a cryptographic protocol must possess several critical properties including scalability, flexibility, incremental deployability, and ability to function in face of imperfect operations. We believe that the insights gained from this study can offer valuable inputs to future cryptographic designs for other Internet-scale systems.

Internet routing tables have been growing rapidly due to factors such as edge-site multihoming, traffic engineering, and disjoint address allocations. To address the routing scalability problems caused by this rapid growth, we propose an evolutionary approach that is incrementally deployable and provides immediate benefits to any adopting ASes. The basic premise of the approach is that route aggregation removes from routing tables the unnecessary topological details about remote portions of the Internet. We demonstrate that aggregation can be applied incrementally starting from local scopes within individual routers and individual ASes, and gradually expanded to the global Internet scope. The evaluation studies show that route aggregation is effective in addressing FIB scalability problems within a router and within a network.

SecSpider is a DNSSEC monitoring system that helps identify operational errors in the DNSSEC deployment and discover unforeseen obstacles. It collects, verifies, and publishes the DNSSEC keys for DNSSEC-enabled zones, which enables operators of both authoritative zones and recursive resolvers to deploy DNSSEC immediately, and benefit from its cryptographic protections. In this paper we present the design and implementation of SecSpider as well as several general lessons that stem from its design and implementation.

This paper describes an unconventional way to apply wireless networking in emerging technologies. It makes the case for using a two-tier hybrid wireless/wired architecture to interconnect hundreds to thousands of cores in chip multiprocessors (CMPs), where current interconnect technologies face severe scaling limitations in excessive latency, long wiring, and complex layout. We propose a recursive wireless interconnect structure called the WCube that features a single transmit antenna and multiple receive antennas at each micro wireless router and offers scalable performance in terms of latency and connectivity. We show the feasibility to build miniature on-chip antennas, and simple transmitters and receivers that operate at 100 − 500 GHz sub-terahertz frequency bands. We also devise new two-tier wormhole based routing algorithms that are deadlock free and ensure a minimum-latency route on a 1000core on-chip interconnect network. Our simulations show that our protocol suite can reduce the observed latency by 20 % to 45%, and consumes power that is comparable to or less than current 2-D wiredmeshdesigns.

During the past twenty years the Domain Name System (DNS) has sustained phenomenal growth while maintaining satisfactory user-level performance. However, the original design focused mainly on system robustness against physical failures, and neglected the impact of operational errors such as mis-configurations. Our measurement efforts have revealed a number of mis-configurations in DNS today: delegation inconsistency, lame delegation, diminished server redundancy, and cyclic zone dependency. Zones with configuration errors suffer from reduced availability and increased query delays up to an order of magnitude. The original DNS design assumed that redundant DNS servers fail independently, but our measurements show that operational choices create dependencies between servers. We found that, left unchecked, DNS configuration errors are widespread. Specifically, lame delegation affects 15% of the measured DNS zones, delegation inconsistency appears in 21% of the zones, diminished server redundancy is even more prevalent, and cyclic dependency appears in 2% of the zones. We also noted that the degrees of mis-configuration vary from zone to zone, with the most popular zones having the lowest percentage of errors. Our results indicate that DNS, as well as any other truly robust large-scale system, must include systematic checking mechanisms to cope with operational errors.

This paper examines the deployment of the DNS Security Extensions (DNSSEC), which adds cryptographic protection to DNS, one of the core components in the Internet infrastructure. We analyze the data collected from the initial DNSSEC deployment which started over 2 years ago, and identify three critical metrics to gauge the deployment: availability, verifiability, and validity. Our results provide the first comprehensive look at DNSSEC’s deployment and reveal a number of challenges that were not anticipated in the design but have become evident in the deployment. First, obstacles such as middle-boxes (firewalls, NATs, etc.) that exist in today’s Internet infrastructure have proven to be problematic and have resulted in unforeseen availability problems. Second, the public-key delegation system of DNSSEC has not evolved as it was hoped and it currently leaves over 97 % of DNSSEC zones isolated and unverifiable, unless some external key authentication mechanism is added. Furthermore, our results show that cryptographic verification is not equivalent to validation; a piece of verified data can still contain the wrong value. Finally, our results demonstrate the essential role of monitoring and measurement in the DNSSEC deployment. We believe that the observations and lessons from the DNSSEC deployment can provide insights into measuring future Internet-scale cryptographic systems.

Despite significant efforts to obtain an accurate picture of the Internet's actual connectivity structure at the level of individual autonomous systems (ASes), much has remained unknown in terms of the quality of the inferred AS maps that have been widely used by the research community. In this paper we assess the quality of the inferred Internet maps through case studies of a set of ASes. These case studies allow us to establish the ground truth of AS-level Internet connectivity between the set of ASes and their directly connected neighbors. They also enable a direct comparison between the ground truth and inferred topology maps and yield new insights into questions such as which parts of the actual topology are adequately captured by the inferred maps, and which parts are missing and why. This information is critical in assessing for what kinds of real-world networking problems the use of currently inferred AS maps or proposed AS topology models are, or are not, appropriate. More importantly, our newly gained insights also point to new directions towards building realistic and economically viable Internet topology maps.

Abstract This paper assesses BitTorrent's robustness against selfish peers who try to download content faster than their fair share by abusing existing protocol mechanisms. We present three exploits that can deliver potential benefits to a selfish peer and evaluate their impact on both public and private download sessions. Our results show that BitTorrent is quite robust against these exploits. Although selfish peers can sometimes attain high download throughput and compliant peers' download rates suffer slightly in consequence, we observe no significant degradation of the overall system's quality of service. We identify scenarios where a selfish peer could attain significant benefits at the expense of compliant peers, and discuss the protocol characteristics that render these scenarios unlikely and hence lead to the system's robustness. Copyright © 2007 John Wiley & Sons, Ltd.

A prefix hijack attack involves an attacker announcing victim networks' IP prefixes into the global routing system. As a result, data traffic from portions of the Internet can be diverted to attacker networks. Prefix hijack attacks are a serious security threat in the Internet and it is important to understand the factors that affect the resiliency of victim networks against these attacks. In this paper, we conducted a systematic study to gauge the effectiveness of prefix hijacks launched at different locations in the Internet topology. Our study shows that direct customers of multiple tier-1 networks are the most resilient, even more than the tier-1 networks themselves. Conversely, if these customer networks are used to launch prefix hijacks, they would also be the most effective launching pads for attacks. We verified our results through case studies using real prefix hijack incidents that had occurred in the Internet.

The Domain Name System (DNS) is a critical Internet infrastructure that provides name to address mapping services. In the past few years, distributed denial of service (DDoS) attacks have targeted the DNS infrastructure and threaten to disrupt this critical service. In this paper we show that the existing DNS can gain significant resilience against DDoS attacks through a simple change to the current DNS operations, by setting longer time-to-live values for a special class of DNS resource records, the infrastructure records. These records are used to navigate the DNS hierarchy and change infrequently. Furthermore, in combination with a set of simple and incrementally deployable record renewal policies, the DNS service availability can be improved by one order of magnitude. Our approach requires neither additional physical resources nor any change to the existing DNS design. We evaluate the effectiveness of our proposed enhancement by using DNS traces collected from multiple locations.

The global Internet routing infrastructure is a large and complex distributed system where routing changes occur constantly. Our objective in this paper is to develop a simple and effective inference solution that can identify the AS or inter-AS link failures that trigger large scale routing changes in near realtime. We achieve this goal through a novel approach based on link weights. We measure the weight of each inter-AS link by the number of routes carried over that link, and keep track of its expected value and variance. We then correlate the weight changes of adjacent links and use a min-cut heuristic to find candidates for the origin of change. This work makes three contributions. First, we keep track of link weights rather than the routes of individual prefixes and thus our analysis is based on an aggregate view. Second, we use expected value and mean deviation of the link weights to identify routing events and distinguish route changes caused by failures from those by recoveries. Finally we use a min-cut heuristic based on the classification of routing events to accurately identify the AS or inter-AS link most likely responsible for the observed route changes. We verified our design using BGP data collected from operational Internet. Our efficient and accurate routing diagnosis solution can greatly help us gain better understanding of the dynamics in the operational Internet.

In this paper we propose a new routing protocol and address scheme, geographically informed inter-domain routing (GIRO). GIRO departs from previous geographic addressing proposals in that it uses geographic information to assist, not to replace, the provider-based IP address allocation and policy-based routing. We show that, by incorporating geographic information into the IP address structure, GIRO can significantly improve the scalability and performance of the global Internet routing system. Within the routing policy constraints, geographic information enables the selection of shortest available routing paths. We evaluate GIRO'S performance through simulations using a Rocketfuel-measured Internet topology. Our results show that, compared to the current practice, GIRO can reduce the geographic distance for 70% of the existing BGP paths, and the reduction is more than 40% for about 20% of the paths. Furthermore, encoding geographic information into IP addresses also enables GIRO to apply geographical route aggregation, and a combination of geographic and topological aggregation can lead to 75% reduction of the current BGP routing table size.

Characterizing the evolution of Internet topology is important to our understanding of the Internet architecture and its interplay with technical, economic and social forces. A major challenge in obtaining empirical data on topology evolution is to identify real topology changes from the observed topology changes, since the latter can be due to either topology changes or transient routing dynamics. In this paper, we formulate the topology liveness problem and propose a solution based on the analysis of BGP data. We find that the impact of transient routing dynamics on topology observation decreases exponentially over time, and that the real topology dynamics consist of a constant-rate birth process and a constant-rate death process. Our model enables us to infer real topology changes from observation data with a given confidence level. We demonstrate the usefulness of the model by applying it to three applications: providing more accurate views of the topology, evaluating theoretical evolution models, and empirically characterizing the trends of topology evolution. We find that customer networks and provider networks have distinct evolution trends, which can provide an important input to the design of future Internet routing architecture.

Peer-to-peer protocols play an increasingly instrumental role in Internet content distribution. It is therefore important to gain a complete understanding of how these protocols behave in practice and how their operating parameters affect overall system performance. This paper presents the first detailed experimental investigation of the peer selection strategy in the popular BitTorrent protocol. By observing more than 40 nodes in instrumented private torrents, we validate three protocol properties that, though believed to hold, have not been previously demonstrated experimentally: the clustering of similar-bandwidth peers, the effectiveness of BitTorrent's sharing incentives, and the peers' high uplink utilization. In addition, we observe that BitTorrent's modified choking algorithmin seed state provides uniform service to all peers, and that an underprovisioned initial seed leads to absence of peer clustering and less effective sharing incentives. Based on our results, we provide guidelines for seed provisioning by content providers, and discuss a tracker protocol extension that addresses an identified limitation of the protocol.

Data dissemination is an indispensible protocol component for the emerging large-scale sensor networks. In this paper, we propose a secure data dissemination protocol that enhances directed diffusion to operate in the presence of compromised sensors. Our proposed solution, secure diffusion, utilizes a novel security primitive called location-binding keys, and exploits the available end-to-end feedback loop in directed diffusion. In secure diffusion, sensor nodes use pairwise neighbor keys to establish secure gradients, and the sink uses location-binding keys to authenticate the received sensing data. By differentiating authentic data from fabricated ones, the sink can selectively reinforce data paths and assist intermediate nodes in local reinforcement decisions to combat compromised nodes. Our security analysis shows that, in the presence of compromised nodes, secure diffusion can ensure both high-quality delivery of authentic data and local containment of malicious traffic.

A number of previous measurement studies [10, 12, 17] have shown the existence of path exploration and slow convergence in the global Internet routing system, and a number of protocol enhancements have been proposed to remedy the problem [21, 15, 4, 20, 5]. However all the previous measurements were conducted over a small number of testing prefixes. There has been no systematic study to quantify the pervasiveness of BGP slow convergence in the operational Internet, nor there is any known effort to deploy any of the proposed solutions.In this paper we present our measurement results from identifying BGP slow convergence events across the entire global routing table. Our data shows that the severity of path exploration and slow convergence varies depending on where prefixes are originated and where the observations are made in the Internet routing hierarchy. In general, routers in tier-1 ISPs observe less path exploration, hence shorter convergence delays than routers in edge ASes, and prefixes originated from tier-1 ISPs also experience less path exploration than those originated from edge ASes. Our data also shows that the convergence time of route fail-over events is similar to that of new route announcements, and significantly shorter than that of route failures, which confirms our earlier analytical results [19]. In addition, we also developed a usage-time based path preference inference method which can be used by future studies of BGP dynamics.

The current Domain Name System (DNS) follows a hierarchical tree structure. Several recent efforts proposed to re-implement DNS as a peer-to-peer network with a flat structure that uses Distributed Hash Tables (DHT) to improve the system availability. In this paper we compare the performance and availability of these two designs, enabled by caching and redundancy in both cases. We show that the caching and redundancy mechanisms in each design are closely bound to its system structure. We further demonstrate that each of the two system structures provides unique advantages over the other, while each has its own shortcomings. Using analysis and tracedriven simulations, we show that hierarchical structure enables high performance caching and that DHT structures provide high degree of robustness against targeted attacks. We further show that the current DNS design offers engineering flexibilities which have been utilized to optimize system performance under typical Internet failures and traffic loads, and which can be further extended to overcome DNS weaknesses against the aforementioned attacks.

Securing wireless networks poses unique research challenges. In this paper, we survey the state-of-the-art approaches to providing security for three popular wireless networking paradigms, namely, IEEE 802.11 based WLANs, third-generation cellular networks, and mobile ad hoc networks. We identify the security threats as well as examine the current solutions. We further summarize lessons learned, discuss open issues, and identify future research directions.

Today's Internet provides a global data delivery service to millions of end users and routing protocols play a critical role in this service. It is important to be able to identify and diagnose any problems occurring in Internet routing. However, the Internet's sheer size makes this task difficult. One cannot easily extract out the most important or relevant routing information from the large amounts of data collected from multiple routers. To tackle this problem, we have developed Link-Rank, a tool to visualize Internet routing changes at the global scale. Link-Rank weighs links in a topological graph by the number of routes carried over each link and visually captures changes in link weights in the form of a topological graph with adjustable size. Using Link-Rank, network operators can easily observe important routing changes from massive amounts of routing data, discover otherwise unnoticed routing problems, understand the impact of topological events, and infer root causes of observed routing changes.

We conduct a systematic study on the pervasiveness and persistency of one specific phenomenon in the global routing system: a small set of highly active prefixes accounts for a large number of routing updates. Our data analysis shows that this phenomenon is commonly observed from monitors in many different ISPs, and exists throughout our 3-year study period. The analysis further shows that the majority of these prefixes are highly active for only one or a few days, while a small number of them are persistently active over long period of time. Case studies demonstrate that the causes of these high routing activity include topological failures, BGP path exploration, protocol defects, and the failure of turning on protection mechanisms.

The number of multi-homed user sites has been rapidly increasing in recent years, where a campus or company network is connected to multiple Internet service providers' networks to improve Internet service reliability. In this paper, we examine the impact of multi-homing via BGP on routing stability and network reliability. More specifically, we compare single-homed prefixes with multi-homed prefixes in terms of the number of routing update messages and the duration of unreachability. Our results show that, on average, single-homed prefixes both generates fewer routing updates than multi-homed prefixes, and provide higher reliability than 97% of multi-homed prefixes (which have a low degree of multi-homing). These results suggest the need to further improve BGP's stability to enable Internet users to gain the expected reliability benefit from multi-homing.

Route Flap Damping is a mechanism generally used in network routing protocols. Its goal is to limit the global impact of unstable routes by temporarily suppressing routes with rapid changes over short time periods. Although route damping is a clearly defined and simple procedure at each router, its effect in a large network setting is not well understood. We show that the current damping design leads to the intended behavior only under persistent route flapping. When the number of flaps is small, the global routing dynamics deviates significantly from the expected behavior with a longer convergence delay. Previous work observed that a single route flap can falsely trigger route suppression due to path exploration. However our simulations show that this false suppression only accounts for 30% of the convergence delay after a single route flap. Our study reveals previously unknown interactions between reuse timers at different routers. Route suppression and reuse at different routers are triggered at different times and thus affect the number of updates received by other routers. In turn, this impacts other routers’ damping behavior. We propose to use Root Cause Notification to eliminate both false suppression and undesirable timer interaction.

In a large-scale sensor network individual sensors are subject to security compromises. A compromised node can be used to inject bogus sensing reports. If undetected, these bogus reports would be forwarded to the data collection point (i.e., the sink). Such attacks by compromised nodes can result in not only false alarms but also the depletion of the finite amount of energy in a battery powered network. In this paper, we present a statistical en-route filtering (SEF) mechanism to detect and drop false reports during the forwarding process. Assuming that the same event can be detected by multiple sensors, in SEF each of the detecting sensors generates a keyed message authentication code (MAC) and multiple MACs are attached to the event report. As the report is forwarded, each node along the way verifies the correctness of the MAC's probabilistically and drops those with invalid MACs. SEF exploits the network scale to filter out false reports through collective decision-making by multiple detecting nodes and collective false detection by multiple forwarding nodes. We have evaluated SEF's feasibility and performance through analysis, simulation, and implementation. Our results show that SEF can be implemented efficiently in sensor nodes as small as Mica2. It can drop up to 70% of bogus reports injected by a compromised node within five hops, and reduce energy consumption by 65% or more in many cases.

This paper studies TCP performance in a stationary multihop wireless network using IEEE 802.11 for channel access control. We first show that, given a specific network topology and flow patterns, there exists an optimal window size W* at which TCP achieves the highest throughput via maximum spatial reuse of the shared wireless channel. However, TCP grows its window size much larger than W* leading to throughput reduction. We then explain the TCP throughput decrease using our observations and analysis of the packet loss in an overloaded multihop wireless network. We find out that the network overload is typically first signified by packet drops due to wireless link-layer contention, rather than buffer overflow-induced losses observed in the wired Internet. As the offered load increases, the probability of packet drops due to link contention also increases, and eventually saturates. Unfortunately the link-layer drop probability is insufficient to keep the TCP window size around W'*. We model and analyze the link contention behavior, based on which we propose link RED that fine-tunes the link-layer packet dropping probability to stabilize the TCP window size around W*. We further devise adaptive pacing to better coordinate channel access along the packet forwarding path. Our simulations demonstrate 5 to 30 percent improvement of TCP throughput using the proposed two techniques.

This paper presents a scalable mechanism, fast routing table recovery (FRTR), for detecting and correcting route inconsistencies between neighboring BGP routers. The large size of today's global routing table makes the conventional periodic update approach, used by most routing protocols, infeasible. FRTR lets neighboring routers periodically exchange Bloom filter digests of their routing state. The digest exchanges not only enable the detection of potential inconsistencies during normal operations, but also speed up recovery after a BGP session reset. FRTR achieves low bandwidth overhead by using small digests, and it achieves strong consistency by "salting" the digests with random seeds to remove false-positives. Our analysis and simulation results show that, with one round of message exchanges, FRTR can detect and recover over 91% of random errors that the current BGP would have missed with an overhead as low as 1.3% of a full routing table exchange. With salted digests FRTR can detect and recover all the errors with a probability close to 100% after a few rounds of message exchanges.

Hierarchical systems have been widely used to provide scalable distributed services in the Internet. Unfortunately, such a service hierarchy is vulnerable to DoS attacks. This paper presents HOURS that achieves DoS resilience in an open service hierarchy. HOURS ensures high degree of service accessibility for each surviving node by: 1) augmenting the service hierarchy with hierarchical overlay networks with rich connectivity; 2) making the connectivity of each overlay highly unpredictable; and 3) recovering the overlay when its normal operations are disrupted. We analyze an HOURS-protected open service hierarchy, and demonstrate its high degree of resilience to even large-scale, topology-aware DoS attacks.

One important performance measure for routing protocols is packet delivery. An ideal routing protocol should quickly adapt to topological changes and deliver packets as long as any path to the destination exists. In this paper, we examine the packet delivery performance in a network running the BGP routing protocol when a destination may be disconnected from time to time. We develop two metrics, extra downtime and false uptime, to capture the time difference between actual loss of connectivity and perceived unreachability. Our results show that extra downtime closely matches T/sub up/ convergence delay, and false uptime closely matches T/sub down/ convergence delay. Furthermore, our results show that, for transient connectivity failures, a shorter T/sub down/ convergence time can have negative impact on packet delivery.

Overlay networks represent an emerging technology for rapid deployment of novel network services and applications. However, since public overlay networks are built out of loosely coupled end-hosts, individual nodes are less trustworthy than Internet routers in carrying out the data forwarding function. Here we describe a set of mechanisms designed to detect and repair errors in the data stream. Utilizing the highly redundant connectivity in overlay networks, our design splits each data stream to multiple sub-streams which are delivered over disjoint paths. Each sub-stream carries additional information that enables receivers to detect damaged or lost packets. Furthermore, each node can verify the validity of data by periodically exchanging Bloom filters, the digests of recently received packets, with other nodes in the overlay. We have evaluated our design through both simulations and experiments over a network testbed. The results show that most nodes can effectively detect corrupted data streams even in the presence of multiple tampering nodes.

Measurements have shown evidences of inter-domain packet forwarding loops in the Internet, but the exact cause of these loops remains unclear. As one of the efforts in identifying the causes, this paper examines how transient loops can be created at the inter-domain level via BGP, and what are the major factors that contribute to duration of the routing loops. As a path-vector routing protocol, BGP messages list the entire AS path to each destination and the path information enables each node to detect, thus break, arbitrarily long routing loops involving itself. However, delays due to physical constrains and protocol mechanisms slow down routing updates propagation and the routing information inconsistencies among the nodes lead to loop formation during convergence. We show that the duration of transient BGP loops match closely to BGP's routing convergence time and the looping duration is linearly proportional to BGP's minimum route advertisement interval timer (MRAI) value. We also examine four BGP routing convergence enhancements and show that two enhancements effective in speeding up routing convergence are also effective in reducing routing loops.

In a large-scale sensor network individual sensors are subject to security compromises. A compromised node can inject into the network large quantities of bogus sensing reports which, if undetected, would be forwarded to the data collection point (i.e. the sink). Such attacks by compromised sensors can cause not only false alarms but also the depletion of the finite amount of energy in a battery powered network. We present a statistical en-route filtering (SEF) mechanism that can detect and drop such false reports. SEF requires that each sensing report be validated by multiple keyed message authentication codes (MACs), each generated by a node that detects the same event. As the report is forwarded, each node along the way verifies the correctness of the MACs probabilistically and drops those with invalid MACs at earliest points. The sink further filters out remaining false reports that escape the en-route filtering. SEF exploits the network scale to determine the truthfulness of each report through collective decision-making by multiple detecting nodes and collective false-report-detection by multiple forwarding nodes. Our analysis and simulations show that, with an overhead of 14 bytes per report, SEF is able to drop 80/spl sim/90% injected false reports by a compromised node within 10 forwarding hops, and reduce energy consumption by 50% or more in many cases.

Wireless sensor networks are characterized by collections of small, low-power nodes that collect information about the physical world. Concurrent transmissions caused by the well-known hidden terminal problem result in collisions and packet corruption. Since corrupted packets must be retransmitted, collisions add an additional burden to the already energy constrained system. We present an application-based approach to collision avoidance. We propose two specific algorithms; the first one follows TCP's congestion avoidance algorithm and adjusts the transmission rate when a collision occurs, while the second one shifts packet transmission times to minimize collisions. We evaluated both algorithms through simulations and our results show that our approach can reduce the number of collision-induced retransmissions by a factor of 8 and the energy consumption by up to 50%.

Failures at the BGP level can have significant impact on the overall Internet. Understanding the behavior of BGP is thus both an important practical challenge and an interesting research problem. To understand the true dynamics, and help interpret the multiple gigabytes of BGP log data, we have developed the "Link-Rank" graphical toolset. Link-Rank weighs the links between autonomous systems by the number of routing prefixes going through each link. Tracing these graphs over time results in a directed graph that shows the weight changes of the logical inter-AS links. From this graph one can easily visualise the complex BGP path changes and also combine views from multiple vantage points, to get a better picture of global routing dynamics. We illustrate the usefulness of Link-Rank by using it to examine BGP routing dynamics in three example cases. These examples show Link-Rank is able to help BGP analysts estimate the scope of routing changes and to reveal important routing dynamics in the presence of superfluous BGP update messages.

Due to the Internet's sheer size, complexity, and various routing policies, it is difficult if not impossible to locate the causes of large volumes of BGP update messages that occur from time to time. To provide dependable global data delivery we need diagnostic tools that can pinpoint the exact connectivity changes. We describe an algorithm, called MVSChange that can pin down the origin of routing changes due to any single link failure or link restoration. Using a simplified model of BGP, called simple path vector protocol (SPVP), and a graph model of the Internet, MVSChange takes as input the SPVP update messages collected from multiple vantage points and accurately locates the link that initiated the routing changes. We provide theoretical proof for the correctness of the design.

During the past twenty years the Domain Name System (DNS) has sustained phenomenal growth while maintaining satisfactory performance. However, the original design focused mainly on system robustness against physical failures, and neglected the impact of operational errors such as misconfigurations. Our recent measurement effort revealed three specific types of misconfigurations in DNS today: lame delegation, diminished server redundancy, and cyclic zone dependency. Zones with configuration errors suffer from reduced availability and increased query delays up to an order of magnitude. Furthermore, while the original DNS design assumed that redundant DNS servers fail independently, our measurements show that operational choices made at individual zones can severely affect the availability of other zones. We found that, left unchecked, DNS configuration errors are widespread, with lame delegation affecting 15% of the DNS zones, diminished server redundancy being even more prevalent, and cyclic dependency appearing in 2% of the zones. We also noted that the degrees of misconfiguration vary from zone to zone, with most popular zones having the lowest percentage of errors. Our results indicate that DNS, as well as any other truly robust large-scale system, must include systematic checking mechanisms to cope with operational errors.

Restricting network access of routing and packet forwarding to well-behaving nodes and denying access from misbehaving nodes are critical for the proper functioning of a mobile ad-hoc network where cooperation among all networking nodes is usually assumed. However, the lack of a network infrastructure, the dynamics of the network topology and node membership, and the potential attacks from inside the network by malicious and/or noncooperative selfish nodes make the conventional network access control mechanisms not applicable. We present URSA, a ubiquitous and robust access control solution for mobile ad hoc networks. URSA implements ticket certification services through multiple-node consensus and fully localized instantiation. It uses tickets to identify and grant network access to well-behaving nodes. In URSA, no single node monopolizes the access decision or is completely trusted. Instead, multiple nodes jointly monitor a local node and certify/revoke its ticket. Furthermore, URSA ticket certification services are fully localized into each node's neighborhood to ensure service ubiquity and resilience. Through analysis, simulations, and experiments, we show that our design effectively enforces access control in the highly dynamic, mobile ad hoc network.

This paper studies the problem of electing a small number of representatives (council) out of a (possible large) group of anonymous candidates. The problem arises in scenarios such as multicast where, to avoid feedback implosion, a small subset of the receivers is chosen to provide feedback on network conditions. We present several algorithms for this problem and analyze the expected number of messages and rounds required for their convergence. In particular, we present an algorithm that almost always converges in one round using a small number of messages (for typical council size) when the number of hosts is known. In the case where the number of hosts is unknown (and too large to be polled), our algorithms converge in a small number of rounds that improves previous results by Bolot et al. (1994).

Internet measurements have shown that network failures happen frequently, and that existing routing protocols can take multiple seconds, or even minutes, to converge after a failure. During these routing convergence periods, some packets may already be en-route to their destinations and new packets may be sent. These in-ight packets can en-counter routing loops, delays, and losses. However, little is known about how many packets are delivered (or not de-livered) during routing convergence periods. In this paper, we study the impact of topological connec-tivity and routing protocol designs on the packet delivery during routing convergence. We examine three distributed routing protocols: RIP, Distributed Bellman Ford and BGP through protocol analysis and simulation experiments. Our study shows that the packet delivery ratio improves as the network connectivity becomes richer. However differences in routing protocol designs impact their ability to fully uti-lize the topological redundancy in face of component fail-ures. Two factors in routing protocol design, keeping al-ternate path information at each router and quickly prop-agating new reachability information, appear to have the most impact on the packet delivery behavior during con-vergence. 1

Traditional routing protocol designs have focused solely on the functionality of the protocols and implicitly assume that all routing update messages received by a router carry valid information. However operational experience suggests that hardware faults, software implementation bugs, operator misconfigurations, let alone malicious attacks can all lead to invalid routing protocol announcements. Although several recent efforts have developed cryptography-based authentication for routing protocols, such enhancements alone are rendered ineffective in the face of faults caused by misconfigurations or hardware/software errors. In this paper we develop a simple routing update validation algorithm for the RIP protocol, RIP with triangle theorem checking and probing (RIP-TP). In RIP-TP routers utilize a triangle theorem to identify suspicious new routing announcements, and then use probing messages to verify the correctness of the announcements. We have evaluated the effectiveness of RIP-TP through simulation using various faulty node behaviors, link failure dynamics and network sizes. The results show that, with an overhead as low as about one probing message per received update message in the worst case, RIP-TP can effectively detect 95% or more invalid routing announcements.

The Domain Name System (DNS) is an essential part of the Internet infrastructure and provides fundamental services, such as translating host names into IP addresses for Internet communication. The DNS is vulnerable to a number of potential faults and attacks. In particular, false routing announcements can deny access to the DNS service or redirect DNS queries to a malicious impostor Due to the hierarchical DNS design, a single fault or attack against the routes to any of the top level DNS servers can disrupt Internet services to millions of users. In this paper we propose a path-filtering approach to protect the routes to the critical top level DNS servers. Our approach exploits the high degree of redundancy in top level DNS servers and also exploits the observation that popular destinations, including top level DNS servers, are well connected via stable routes. Our path-filter restricts the potential top level DNS server route changes to be within a set of established paths. Heuristics derived from routing operations are used to adjust the potential routes overtime. We tested our path-filtering design against BGP routing logs and the results show that the design can effectively ensure correct routes to top level DNS servers without impacting DNS service availability.

In this paper we present PEAS, a robust energy-conserving protocol that can build long-lived, resilient sensor networks using a very large number of small sensors with short battery lifetime. PEAS extends the network lifetime by maintaining a necessary set of working nodes and turning off redundant ones. PEAS operations are based on individual node's observation of the local environment and do not require any node to maintain per neighbor node state. PEAS performance possesses a high degree of robustness in the presence of both node power depletions and unexpected failures. Our simulations and analysis show that PEAS can maintain an adequate working node density in the face of up to 38% node failures, and it can maintain roughly a constant overhead level under various deployment conditions ranging from sparse to very dense node deployment by using less than 1% of total energy consumption. As a result, PEAS can extend a sensor network's functioning time in linear proportion to the deployed sensor population.

This paper studies TCP performance over multihop wireless networks that use the IEEE 802.11 protocol as the access method. Our analysis and simulations show that, given a specific network topology and flow patterns, there exists a TCP window size W*, at which TCP achieves best throughput via improved spatial channel reuse. However, TCP does not operate around W*, and typically grows its average window size much larger; this leads to decreased throughput and increased packet loss. The TCP throughput reduction can be explained by its loss behavior. Our results show that network overload is mainly signified by wireless link contention in multihop wireless networks. As long as the buffer size at each node is reasonably large (say, larger than 10 packets), buffer overflow-induced packet loss is rare and packet drops due to link-layer contention dominate. Link-layer drops offer the first sign for network overload. We further show that multihop wireless links collectively exhibit graceful drop behavior: as the offered load increases, the link contention drop probability also increases, but saturates eventually. In general, the link drop probability is insufficient to stabilize the average TCP window size around W*. Consequently, TCP suffers from reduced throughput due to reduced spatial reuse. We further propose two techniques, link RED and adaptive pacing, through which we are able to improve TCP throughput by 5% to 30% in various simulated topologies. Some simulation results are also validated by real hardware experiments.

The Internet distance map service (IDMaps) [P. Francis, S. Jamin, C. Jin, D. Raz, Y. Shavitt, and L. Zhang, 2001] provides distance estimates between any pair of hosts connected to the Internet. The IDMaps system comprises two component types: tracers that measure distance between IP address prefixes, and servers that collect measurement results and answer distance queries. The distance information protocol (DIP) is used for tracers to report measured distance data to servers. The dynamics on the Internet topology, the distributed nature of autonomous tracers and servers, and the vast size of the data set require that DIP provide highly adaptive and scalable data dissemination from tracers to servers. DIP is a soft-state announce/listen protocol and scales independently from the total amount of measurement data by all tracers. DIP achieves its scalability through combination of staged timers, positive feedback, and feedback suppression techniques, which enable DIP to disseminate only the most useful measurement data to servers in a dynamic way. Simulations verified DIP's scalability and adaptability under various network conditions.

No abstract available.

The Domain Name System (DNS) is an essential part of the Internet infrastructure and provides fundamental services, such as translating host names into IP addresses for Internet communication. The DNS is vulnerable to a number of potential faults and attacks. In particular, false routing announcements can deny access to the DNS service or redirect DNS queries to a malicious impostor. Due to the hierarchical DNS design, a single fault or attack against the routes to any of the top-level DNS servers can disrupt Internet services to millions of users. We propose a path-filtering approach to protect the routes to the critical top-level DNS servers. Our approach exploits both the high degree of redundancy in top-level DNS servers and the observation that popular destinations, including top-level DNS servers, are well-connected via stable routes. Our path-filter restricts the potential top-level DNS server route changes to be within a set of established paths. Heuristics derived from routing operations are used to adjust the potential routes over time. We tested our path-filtering design against BGP routing logs and the results show that the design can effectively ensure correct routes to top-level DNS servers without impacting DNS service availability.

Network measurement has shown that a specific IP address prefix may be announced by more than one autonomous system (AS), a phenomenon commonly referred to as Multiple Origin AS, or MOAS. MOAS can be due to either operational need to support multi-homing, or false route announcements due to configuration or implementation errors, or even by intentional attacks. Packets following such bogus routes will be either dropped or in the case of an intentional attack, delivered to a machine of the attacker's choosing. The paper presents a protocol enhancement to BGP which enables BGP to detect bogus route announcements from false origins. Rather than imposing cryptography-based authentication and encryption to secure routing message exchanges, our solution makes use of the rich connectivity among ASs that exists in the Internet. Simulation results show that this simple solution can effectively detect false routing announcements even in the presence of multiple compromised routers, become more robust in larger topologies, and can substantially reduce the impact of false routing announcements even with a partial deployment.

Small, inexpensive sensors with limited memory, computing power and short battery lifetimes are turning into reality. Due to adverse conditions such as high noise levels, extreme humidity or temperatures, or even destructions from unfriendly entities, sensor node failures may become norms rather than exceptions in real environments. To be practical, sensor networks must last for much longer times than that of individual nodes, and have yet to be robust against potentially frequent node failures. This paper presents the design of PEAS, a simple protocol that can build a long-lived sensor network and maintain robust operations using large quantities of economical, short-lived sensor nodes. PEAS extends system functioning time by keeping only a necessary set of sensors working and putting the rest into sleep mode. Sleeping ones wake up now and then, probing the local environment and replacing failed ones. The sleeping periods are self-adjusted dynamically, so as to keep the sensors' wakeup rate roughly constant, thus adapting to high node densities.

Despite BGP's critical importance as the de-facto Internet inter-domain routing protocol, there is little understanding of how BGP actually performs under stressful conditions when dependable routing is most needed. In this paper, we examine BGP's behavior during one stressful period, the Code Red/Nimda attack on September 18, 2001. The attack was correlated with a 30-fold increase in the BGP update messages at a monitoring point which peers with a number of Internet service providers. Our examination of BGP's behavior during the event concludes that BGP exhibited no significant abnormality, and that over 40% of the observed updates can be attributed to the monitoring artifact in current BGP measurement settings. Our analysis, however, does reveal several weak points in both the protocol and its implementation, such as BGP's sensitivity to the transport session reliability, its inability to avoid the global propagation of small local changes, and its certain implementation features whose otherwise benign effects only get amplified under stressful conditions. We also identify areas for improvement in the current network measurement and monitoring effort.

Forcing all IP packets to carry correct source addresses can greatly help network security, attack tracing, and network problem debugging. However, due to asymmetries in today's Internet routing, routers do not have readily available information to verify the correctness of the source address for each incoming packet. In this paper we describe a new protocol, named SAVE, that can provide routers with the information needed for source address validation. SAVE messages propagate valid source address information from the source location to all destinations, allowing each router along the way to build an incoming table that associates each incoming interface of the router with a set of valid source address blocks. This paper presents the protocol design and evaluates its correctness and performance by simulation experiments. The paper also discusses the issues of protocol security, the effectiveness of partial SAVE deployment, and the handling of unconventional forms of network routing, such as mobile IP and tunneling.

This paper presents a new mechanism for improving the convergence properties of path vector routing algorithms, such as BGP. Using a route's path information, we develop two consistency assertions for path vector routing algorithms that are used to compare similar routes and identify infeasible routes. To apply these assertions in BGP, mechanisms to signal failure/policy withdrawal, and traffic engineering are provided. Our approach was implemented and deployed in a BGP testbed and evaluated using simulation. By identifying and ignoring the infeasible routes, we achieved substantial reduction in both BGP convergence time and the total number of intermediate route changes.

While the advantages of multicast delivery over multiple unicast deliveries is undeniable, the deployment of the IP multicast protocol has been limited to "islands" of network domains under single administrative control. Deployment of inter-domain multicast delivery has been slow due to both technical and administrative reasons. In this paper we propose a Host Multicast Tree Protocol (HMTP) that (1) automates the interconnection of IP-multicast enabled islands and (2) provides multicast delivery to end hosts where IP multicast is not available. With HMTP, end-hosts and proxy gateways of IP multicast-enabled islands can dynamically create shared multicast trees across different islands. Members of an HMTP multicast group self-organize into an efficient, scalable and robust multicast tree. The tree structure is adjusted periodically to accommodate changes in group membership and network topology. Simulation results show that the multicast tree has low cost, and data delivered over it experiences moderately low latency.

Mobile ad hoc networking offers convenient infrastructure-free communication over the shared wireless channel. However, the nature of ad hoc networks makes them vulnerable to security attacks. Examples of such attacks include passive eavesdropping over the wireless channel, denial of service attacks by malicious nodes as well as attacks from compromised nodes or stolen devices. Unlike their wired counterpart, infrastructureless ad hoc networks do not have a clear line of defense, and every node must be prepared for encounters with an adversary. Therefore, a centralized or hierarchical network security solution does not work well. This work provides scalable, distributed authentication services in ad hoc networks. Our design takes a self-securing approach, in which multiple nodes (say, k) collaboratively provide authentication services for any node in the network. This paper follows the design guidelines of [7] and makes several new contributions. We first formalize a localized trust model that lays the foundation for the design, and then expand the adversary model that the system should handle. We further propose refined localized certification services, and develop a new scalable solution of share updates to resist more powerful adversaries. Finally, the new solution is evaluated through simulations. 1

Sink mobility brings new challenges to large-scale sensor networking. It suggests that information about each mobile sink's location be continuously propagated through the sensor field to keep all sensor nodes updated with the direction of forwarding future data reports. Unfortunately frequent location updates from multiple sinks can lead to both excessive drain of sensors' limited battery power supply and increased collisions in wireless transmissions. In this paper we describe TTDD, a Two-Tier Data Dissemination approach that provides scalable and efficient data delivery to multiple mobile sinks. Each data source in TTDD proactively builds a grid structure which enables mobile sinks to continuously receive data on the move by flooding queries within a local cell only. TTDD's design exploits the fact that sensor nodes are stationary and location-aware to construct and maintain the grid structures with low overhead. We have evaluated TTDD performance through both analysis and extensive simulation experiments. Our results show that TTDD handles multiple mobile sinks efficiently with performance comparable with that of stationary sinks.

The large number of networked sensors, frequent sensor failures and stringent energy constraints pose unique design challenges for data forwarding in wireless sensor networks. In this paper, we present a new approach to data forwarding in sensor networks that effectively addresses these design issues. Our approach organizes sensors into a dynamic, self-optimizing multicast tree-based forwarding hierarchy, which is data centric and robust to node failures. We demonstrate the effectiveness of our design through simulations.

Since late 1999, DDoS (distributed denial of service) attack has drawn many attentions from both research and industry communities. Many potential solutions (e.g., ingress filtering, packet marking or tracing, and aggregate-based congestion control or rate limiting) have been proposed to handle this network bandwidth consumption attack. Among them, "ICMP traceback (iTrace)" is currently being considered as an industry standard by the IETF (Internet Engineering Task Force). While the idea of iTrace is very clever, efficient, reasonably secure and practical, it suffers a serious statistic problem such that the chance for "useful" and "valuable" iTrace messages can be extremely small against various types of DDoS attacks. This implies that most of the network resources spent on generating and utilizing iTrace messages will be wasted. Therefore, we propose a simple enhancement called "intention-driven" iTrace, which conceptually introduces an extra bit in the routing and forwarding process. With the new "intention-bit", it is shown that, through our simulation study, the performance of iTrace improves dramatically. This work has been proposed to IETF's ICMP Trace-Back working group.

Wireless sensor networks offer a wide range of challenges to networking research, including unconstrained network scale, limited computing, memory and energy resources, and wireless channel errors. We study the problem of delivering messages from any sensor to an interested client user along the minimum-cost path in a large sensor network. We propose a new cost field based approach to minimum cost forwarding. In the design, we present a novel backoff-based cost field setup algorithm that finds the optimal costs of all nodes to the sink with one single message overhead at each node. Once the field is established, the message, carrying dynamic cost information, flows along the minimum cost path in the cost field. Each intermediate node forwards the message only if it finds itself to be on the optimal path, based on dynamic cost states. Our design does not require an intermediate node to maintain explicit "forwarding path" states. It requires a few simple operations and scales to any network size. We show the correctness and effectiveness of the design by both simulations and analysis.

Recursive hierarchy provides a framework for extending position estimation throughout a sensor network. Given imprecise ranging and inter-node communication, nodes scattered throughout a large volume can estimate their physical locations from a small set of reference nodes using only local information. System coverage increases iteratively, as nodes with newly estimated positions join the reference set, capitalizing on the massive scale of sensor networks. The system frames position estimation as a geometric problem solvable through common nonlinear regression techniques and develops methods for gauging the reliability of position estimates. This provides a flexible framework that can use and enhance a variety of technologies and protocols to produce fine-grained position estimates. A specific model provides a simulation environment showing that over 90% of position estimates are correct to within 3% of the ranging distance with only 5% of the system in the initial reference set.

Providing security support for mobile ad-hoc networks is challenging for several reasons: (a) wireless networks are susceptible to attacks ranging from passive eavesdropping to active interfering, occasional break-ins by adversaries may be inevitable in a large time window; (b) mobile users demand "anywhere, anytime" services; (c) a scalable solution is needed for a large-scale mobile network. In this paper, we describe a solution that supports ubiquitous security services for mobile hosts, scales to network size, and is robust against break-ins. In our design, we distribute the certification authority functions through a threshold secret sharing mechanism, in which each entity holds a secret share and multiple entities in a local neighborhood jointly provide complete services. We employ localized certification schemes to enable ubiquitous services. We also update the secret shares to further enhance robustness against break-ins. Both simulations and implementation confirm the effectiveness of our design.

There is an increasing need to quickly and efficiently learn network distances, in terms of metrics such as latency or bandwidth, between Internet hosts. For example, Internet content providers often place data and server mirrors throughout the Internet to improve access latency for clients, and it is necessary to direct clients to the nearest mirrors based on some distance metric in order to realize the benefit of the mirrors. We suggest a scalable Internet-wide architecture, called IDMaps, which measures and disseminates distance information on the global Internet. Higher level services can collect such distance information to build a virtual distance map of the Internet and estimate the distance between any pair of IP addresses. We present our solutions to the measurement server placement and distance map construction problems in IDMaps. We show that IDMaps can indeed provide useful distance estimations to applications such as nearest mirror selection.

The IDMaps project aims to provide a distance map of the Internet from which relative distances between hosts on the Internet can be gauged. Many distributed systems and applications can benefit from such a distance map service, for example, a common method to improve user-perceived performance of the Internet is to place data and server mirrors closer to clients. When a client tries to access a mirrored server, which mirror should it access? With IDMaps, the closest mirror can be determined based on distance estimates between the client and the mirrors. In this paper we investigate both graph theoretic methods and ad hoc heuristics for instrumenting the Internet to obtain distance maps. We evaluate the efficacy of the resulting distance maps by comparing the determinations of the closest replica using known topologies against those obtained using the distance maps.

Web caching is generally acknowledged as an important service for alleviating focused overloads when certain WWW servers' contents suddenly become popular. Cooperative caching systems are more effective than independent caches due to the larger collective backing store that cooperation creates. One such system currently being developed at UCLA, adaptive Web caching (AWC), uses an application-level forwarding table to locate the nearest copy of a requested URL's contents. This paper describes one specific design in AWC, a simple URL table compression algorithm allowing efficient content information-sharing among neighboring caches. The compression algorithm is based on a hierarchical URL decomposition to aggregate URL sharing common prefixes and an incremental hashing function to minimize collisions between prefixes. The algorithm's collision rate is derived analytically and verified by five sets of Web trace data. The results demonstrate that the collision rate is bounded and has little impact on page fetching latency. Finally, this compression method is compared to the summary cache method.

In this study we investigate the interaction between TCP and MAC layer in a wireless multi-hop network. This type of network has traditionally found applications in the military (automated battlefield), law enforcement (search and rescue) and disaster recovery (flood, earthquake), where there is no fixed wired infrastructure. Wireless "ad-hoc" multi-hop networks have previously been proposed for nomadic computing applications. Key requirements in all the above applications are reliable data transfer and congestion control, features that are generally supported by TCP. Unfortunately, TCP performs on wireless in a much less predictable way than on wired protocols. Using simulation, we provide new insight into two critical problems of TCP over wireless multi-hop. The first is the conflict between data packets and ACKs, which causes TCP performance to degrade for window sizes greater than 1 packet. The second is the interaction between MAC and TCP layer backoff timers which causes severe unfairness and capture conditions. In the paper, we identify these problems in several representative simulation runs on various topologies and traffic patterns and indicate possible remedies to improve TCP efficiency over a wireless multi-hop network.

As a soft-state protocol, RSVP specifies that each RSVP node sends periodic control messages to maintain the state for active RSVP sessions. The protocol overhead due to such periodic messages grows linearly with the number of RSVP sessions. One may reduce the overhead by using a longer refresh period, which unfortunately leads to longer delays in re-synchronizing RSVP state. In this paper we introduce a novel "state-compression" approach to reducing the overhead of periodic refreshes. Instead of per session refresh messages, an RSVP node sends periodically to each of its neighbor node a digest message that contains a compressed version of the entire RSVP state shared with that particular neighbor. In order to speed up state synchronization in face of message losses we also enhance RSVP with an acknowledgment mechanism. Our mechanisms achieve a constant message transmission overhead and low delay while retaining the soft-state nature of the RSVP protocol.

There is an increasing need for Internet hosts to be able to quickly and efficiently learn the distance, in terms of metrics such as latency or bandwidth, between Internet hosts. For example, to select the nearest of multiple equal content Web servers. This paper explores technical issues related to the creation of a public infrastructure service to provide such information. In so doing, we suggest an architecture, called IDMaps, whereby Internet distance information is distributed over the Internet, using IP multicast groups, in the form of a virtual distance map. Systems listening to the groups can estimate the distance between any pair of IP addresses by running a spanning tree algorithm over the received distance map. We also presents the results of experiments that give preliminary evidence supporting the architecture. This work thus lays the initial foundation for future work in this new area.

With advances in packet routing technology, and resource reservation protocols, the Internet is expected to provide ubiquitous integrated transport of speech, audio, video, and other real-time multimedia data in addition to the current best effort data traffic. Such integrated transport will also need to be supported for the increasing number of mobile users who access the Internet over wireless access networks, using Mobile-IP to retain continual IP connectivity. We present a simple quality of service (QoS) signaling protocol for mobile users in an integrated service Internet. The protocol works by combining pre-provisioned RSVP tunnels with Mobile IP. Our protocol, even-though simple, captures the essence of QoS provisioning for wireless and mobile networks. The wireless medium provides a completely different medium than wires, and therefore one's expectations from it should be different. Service quality is inherently mobility dependent, and intermittent disconnections are bound to happen. It is not the signaling protocol's task to completely overcome or conceal transient conditions from applications, but rather applications should try to adapt. Our approach can be easily implemented today with minimal changes to other components of the Internet architecture. We also evaluate the application level performance impact of the QoS provisioning delays associated with our protocol on a prototypical packet speech application with various playout buffering strategies, and compare against the performance of the ordinary RSVP protocol suite with Mobile IP.

Scalable reliable multicast (SRM) is a framework for reliable multicast delivery. In order to maximize the collaboration among the group members in error recovery, both retransmission requests and replies are multicast to the entire group. While SRM effectively uses random timers to suppress duplicate requests and replies, the global nature of the request and replies means that every packet loss results in at least one request and reply message sent to the entire group. To further improve the scalability of SRM, one must localize the scope of error recovery traffic. In this paper, we present two approaches to local recovery: hop-based scope control and use of local recovery groups. The first approach uses hop count to limit the distribution of requests and replies whereas the second approach confines error recovery traffic using separately addressed local recovery groups. The local recovery groups and hop count settings are automatically created and dynamically adjusted based on observed loss patterns. The use simulation experiments to examine the performance of both approaches.

In this paper we propose a multicast protocol for a multihop, mobile wireless network with cluster based routing and token access protocol within each cluster. The multicast protocol uses a shared tree which is dynamically updated to adjust to changes in topology and membership (i.e. dynamic joins and quits). Two options for tree maintenance have been simulated and evaluated: "hard state" (i.e. each connection must be explicitly cleared) and "soft state" (each connection is automatically timed out and must be refreshed). For the soft state policy, the performance of different choices of timeout and refresh timers is first analyzed for a range of node mobility values. Next, soft state and hard state policies are compared based on throughput, join delay, and control overhead criteria.

This paper describes scalable reliable multicast (SRM), a reliable multicast framework for light-weight sessions and application level framing. The algorithms of this framework are efficient, robust, and scale well to both very large networks and very large sessions. The SRM framework has been prototyped in wb, a distributed whiteboard application, which has been used on a global scale with sessions ranging from a few to a few hundred participants. The paper describes the principles that have guided the SRM design, including the IP multicast group delivery model, an end-to-end, receiver-based model of reliability, and the application level framing protocol model. As with unicast communications, the performance of a reliable multicast delivery algorithm depends on the underlying topology and operational environment. We investigate that dependence via analysis and simulation, and demonstrate an adaptive algorithm that uses the results of previous loss recovery events to adapt the control parameters used for future loss recovery. With the adaptive algorithm, our reliable multicast delivery algorithm provides good performance over a wide range of underlying topologies.

Many designs for integrated services networks offer a bounded delay packet delivery service to support real-time applications. To provide a bounded delay service, networks must use admission control to regulate their load. Previous work on admission control mainly focused on algorithms that compute the worst case theoretical queueing delay to guarantee an absolute delay bound for all packets. In this paper, we describe a measurement-based admission control algorithm (ACA) for predictive service, which allows occasional delay violations. We have tested our algorithm through simulations on a wide variety of network topologies and driven with various source models, including some that exhibit long-range dependence, both in themselves and in their aggregation. Our simulation results suggest that measurement-based approach combined with the relaxed service commitment of predictive service enables us to achieve a high level of network utilization while still reliably meeting the delay bound.

The integrated services packet network (ISPN) architecture proposed within the Internet community incorporates a resource reservation mechanism for those applications requiring quality of service (QoS) guarantees. Resource reservation introduces a new form of resource contention that can lead to reduced network throughput and thrashing. We establish several necessary conditions to induce thrashing. We also look at the effects several different reservation models and user behavior can have on network stability. Our work is unique from previous network resource reservation investigations in that we consider the effects of reservations for multipoint-to-multipoint applications. We conclude with examples of how simple modifications to user behavior can result in significant increases in system stability.

This paper describes SRM (Scalable Reliable Multicast), a reliable multicast framework for application level framing and light-weight sessions. The algorithms of this framework are efficient, robust, and scale well to both very large networks and very large sessions. The framework has been prototyped in wb, a distributed whiteboard application, and has been extensively tested on a global scale with sessions ranging from a few to more than 1000 participants. The paper describes the principles that have guided our design, including the IP multicast group delivery model, an end-to-end, receiver-based model of reliability, and the application level framing protocol model. As with unicast communications, the performance of a reliable multicast delivery algorithm depends on the underlying topology and operational environment. We investigate that dependence via analysis and simulation, and demonstrate an adaptive algorithm that uses the results of previous loss recovery events to adapt the control parameters used for future loss recovery. With the adaptive algorithm, our reliable multicast delivery algorithm provides good performance over a wide range of underlying topologies.

Many designs for integrated service networks offer a bounded delay packet delivery service to support real-time applications. To provide bounded delay service, networks must use admission control to regulate their load. Previous work on admission control mainly focused on algorithms that compute the worst case theoretical queueing delay to guarantee an absolute delay bound for all packets. In this paper we describe a measurement-based admission control algorithm for predictive service, which allows occasional delay violations. We have tested our algorithm through simulations on a wide variety of network topologies and driven with various source models, including some that exhibit long-range dependence, both in themselves and in their aggregation. Our simulation results suggest that, at least for the scenarios studied here, the measurement-based approach combined with the relaxed service commitment of predictive service enables us to achieve a high level of network utilization while still reliably meeting the delay bound.

This paper presents a comparative analysis of two resource reservation protocols, ST-II proposed by Topolcic (1990) and resource reservation protocol (RSVP) proposed by Zhang, Braden, Estrin, Herzog and Jamin (1994) in support of an integrated services packet network (ISPN). The authors use simulations to examine the network-wide resource requirements for each protocol to support a number of application communication styles, across a range of group sizes and membership distributions. They also present a comparison of the protocol features to accommodate network and group membership dynamics.>

In recent years, a wide variety of mobile computing devices has emerged, including portables, palmtops, and personal digital assistants. Providing adequate network connectivity for these devices will require a new generation of wireless LAN technology. In this paper we study media access protocols for a single channel wireless LAN being developed at Xerox Corporation's Palo Alto Research Center. We start with the MACA media access protocol first proposed by Karn [9] and later refined by Biba [3] which uses an RTS-CTS-DATA packet exchange and binary exponential back-off. Using packet-level simulations, we examine various performance and design issues in such protocols. Our analysis leads to a new protocol, MACAW, which uses an RTS-CTS-DS-DATA-ACK message exchange and includes a significantly different backoff algorithm.

The role of pricing policies in multiple service class networks is studied. An abstract formulation of service disciplines and pricing policies that allows the interplay between service disciplines and pricing policies in determining overall network performance to be described more clearly is presented. Effective multiclass service disciplines allow networks to focus resources on performance-sensitive applications, while effective pricing policies allows the benefits of multiple service classes to be spread around to all users. Furthermore, the incentives formed by service disciplines and pricing policies must be carefully tuned so that user self-interest leads to optimal overall network performance. These concepts are illustrated through simulation of several simple example networks. It is found that it is possible to set the prices so that users of every application type are more satisfied with the combined cost and performance of a network with service-class-sensitive prices.>

This paper considers the support of real-time applications in an Integrated Services Packet Network (ISPN). We first review the characteristics of real-time applications. We observe that, contrary to the popular view that real-time applications necessarily require a fixed delay bound, some real-time applications are more flexible and can adapt to current network conditions. We then propose an ISPN architecture that supports two distinct kinds of real-time service: guaranteed service, which is the traditional form of real-time service discussed in most of the literature and involves pre-computed worst-case delay bounds, and predicted service which uses the measure performance of the network in computing delay bounds. We then propose a packet scheduling mechanism that can support both of these real-time services as well as accommodate datagram traffic. We also discuss two other aspects of an overall ISPN architecture: the service interface and the admission control criteria.

We study the role of pricing policies in multiple service class networks. We argue that some form of graduated prices are required in order for any multiclass service discipline to have the desired effect. Moreover, we demonstrate through simulation that it is possible to set the prices so that every user is more satisfied with the combined cost and performance of a network with graduated prices. For some users the performance penalty received for requesting a less-than-optimal service class is offset by the reduced price of the service. For the other users the monetary penalty incurred by using the more expensive, higher quality service classes is offset by the improved performance they receive. Thus, prices allow us to spread the benefits of multiple service classes around to all users, rather than just having these benefits remain exclusively with users who are performance sensitive. 1 Introduction Recent research on computer networks has been concerned almost exclusively with the...

We use simulation to study the dynamics of the congestion cent rol algorithm embedded in the BSD 4.3-Tahoe TCP implementation.We investigate the simple case of a few TCP connections, originating and terminating at the same pair of hosts, using a single bottleneck link.This work is an extension of our earlier work ([16]), where one-way traffic (i.e., all of the sources are on the same host and all of the destinations are on the other host) was studied.In this paper we investigate the dynamics that results from two-way traffic (in which there are data sources on both hosts).We find that the one-way traffic clustering and loss-synchronization phenomena d~cussed in [16] persist in this new situation, albeit in a slightly modified form.In addition, there are two new phenomena not present in the earlier study:(1) ACK-compression, which is due to the interaction of data and ACK packets and gives rise to rapid fluctuations in queue length, and (2) an out-of-phase queue-synchronization mode, which keeps link utilization less than optimal even in the limit of very large buffers.These phenomena are helpful in understanding results from an earlier study of network oscillations ([19]).

One of the challenging research issues in building high-speed packet-switched networks is how to control the transmission rate of statistical data flows. This paper describes a new traffic control algorithm, VirtualClock , for high-speed network applications. VirtualClock monitors the average transmission rate of statistical data flows and provides every flow with guaranteed throughput and low queueing delay. It provides firewall protection among individual flows, as in a TDM system, while retaining the statistical multiplexing advantages of packet switching. Simulation results show that the VirtualClock algorithm meets all its design goals.