Drones have carried weapons, drugs, explosives and illegal packages in the recent past, raising strong concerns from public authorities. While existing drone monitoring systems only focus on detecting drone presence, localizing or fingerprinting the drone, there is a lack of a solution for estimating the additional load carried by a drone. In this paper, we present a novel passive RF system, namely DroneScale, to monitor the wireless signals transmitted by commercial drones and then confirm their models and loads. Our key technical contribution is a proposed technique to passively capture vibration at high resolution (i.e., 1Hz vibration) from afar, which was not possible before. We prototype DroneScale using COTS RF components and illustrate that it can monitor the body vibration of a drone at the targeted resolution. In addition, we develop learning algorithms to extract the physical vibration of the drone from the transmitted signal to infer the model of a drone and the load carried by it. We evaluate the DroneScale system using 5 different drone models, which carry external loads of up to 400g. The experimental results show that the system is able to estimate the external load of a drone with an average accuracy of 96.27%. We also analyze the sensitivity of the system with different load placements with respect to the drone's body, flight modes, and distances up to 200 meters.

Several recent studies have shown that router FIB caching offers excellent hit rates with cache sizes that are an order of magnitude smaller than the original forwarding table. However, hit rate alone is not sufficient - other performance metrics such as memory accesses, robustness to cache attacks, queuing delays from cache misses etc., should be considered before declaring FIB caching viable. In this paper, we tackle several pragmatic questions about FIB caching. We characterize cache performance in terms of memory accesses and delay due to cache misses. We study cache robustness to pollution attacks and show that an attacker must sustain packet rates higher than the link capacity to evict the most popular prefixes. We show that caching was robust, even during a recent flare of NTP attacks. We carry out a longitudinal study of cache hit rates over four years and show the hit rate is unchanged over that duration. We characterize cache misses to determine which services are impacted by FIB caching. We conclude that FIB caching is viable by several metrics, not just impressive hit rates.

A variety of solutions have been proposed for detecting and preventing IP hijack attacks. Despite potentially serious consequences these solutions have not been widely deployed, partially because many ISPs do not view their risk as large enough to warrant investment. Nevertheless, a number of organizations such as critical national infrastructure are at a very high risk level and require a deployed solution. Is it possible for these sites to be protected despite the majority apathy, given that a critical mass of ISPs is generally required to participate in the solution? We examine this conflict by presenting an approach which determines AS vulnerability based on topological location. We next examine the effectiveness of incremental security deployment. We separately examine BGP hijack detection which, if improperly peered, may completely miss a hijack. Finally, we address a pessimistic view with respect to deployment and propose an approach in which an autonomous system can act in its own self-interest to determine a minimal threshold for hijack detection or prevention.

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.

This work designs and implements a Not So Cooperative Caching system for Information Centric Networking (ICN). We consider a network comprised of selfish nodes; each is with caching capability and an objective of reducing its own access cost by fetching data from its local cache or from neighboring caches. These nodes would cooperate in caching and sharing content if and only if they each benefit. The challenges are to determine what objects to cache at each node and to implement the system in the context of Named Data Networking (NDN), a large effort that exemplifies ICN. Our results include both a solution for the Not So Cooperative Caching problem and an NDN design and implementation. We evaluate our approach by deploying the system we developed on PlanetLab and show that it improves the content hit ratio by up to 13%.

The Border Gateway Protocol (BGP) is a critical component of the global internet infrastructure. Unfortunately BGP routing was designed with limited regard for security. As a consequence there are many well-documented BGP vulnera- bilities and resulting security exploits. This paper focuses on the design of the Route Origin Verification System (ROVER); a practical solution for detecting and preventing origin and sub-prefix hijacks. ROVER is designed to work with existing systems whenever possible. In particular, ROVER exploits the reverse DNS for storing data and provides a fail-safe, best effort approach to authentication. The approach can be used with a variety of operational models including fully dynamic in-line BGP filtering, periodically updated authenticated route filters, and real-time notifications for network operators. The ROVER system is evaluated using both real operational systems and testbed deployments.

Bot detection methods that rely on deep packet inspection (DPI) can be foiled by encryption. Encryption, however, increases entropy. This paper investigates whether adding highentropy detectors to an existing bot detection tool that uses DPI can restore some of the bot visibility. We present two high-entropy classifiers, and use one of them to enhance BotHunter. Our results show that while BotHunter misses about 50% of the bots when they employ encryption, our high-entropy classifier restores most of its ability to detect bots, even when they use encryption.

Critical services operating over the Internet are increasingly threatened by Distributed Denial of Service (DDoS) attacks. To protect them we propose Epiphany, an architecture that hides the service IP addresses so that attackers cannot locate and target them. Epiphany provides service access through numerous lightweight proxies, presenting a wide target to the attacker. Epiphany has strong location hiding properties; no proxy knows the service address. Instead, proxies communicate over ephemeral paths controlled by the service. If a specific proxy misbehaves or is attacked it can be promptly removed. Epiphany separates proxies into setup and data, and only makes setup proxies public, but these use anycast to create distinct network regions. Clients in clean networks are not affected by attackers in other networks. Data proxies are assigned to clients based on their trust. We evaluate the defense properties of Epiphany using simulations and implementations on PlanetLab and a router testbed.

Recent trends in the networked services industry (e.g., CDN, VPN, VoIP, IPTV) see Internet Service Providers (ISPs) leveraging their existing network connectivity to provide an end-to-end solution. Consequently, new opportunities are available to monitor and improve the end-to-end service quality by leveraging the information from inside the network. We propose a new approach to detect and localize end-to-end service quality issues in such ISP-managed networked services by utilizing traffic data passively monitored at the ISP side, the ISP network topology, routing tables and geographic information. This paper presents the design of a generic service quality monitoring system “Argus”. Argus has been successfully deployed in a tier-1 ISP to monitor millions of users of its CDN service and assist operators to detect and localize end-to-end service quality issues. This operational experience demonstrates that Argus is effective in accurate, quick detection and localization of important service quality issues.

An increasingly diverse set of applications, such as Internet games, streaming videos, e-commerce, online banking, and even mission-critical emergency call services, all relies on IP networks. In such an environment, best-effort service is no longer acceptable. This requires a transformation in network management from detecting and replacing individual faulty network elements to managing the end-to-end service quality as a whole. In this paper, we describe the design and development of a Generic Root Cause Analysis platform (G-RCA) for service quality management (SQM) in large IP networks. G-RCA contains a comprehensive service dependency model that incorporates topological and cross-layer relationships, protocol interactions, and control plane dependencies. G-RCA abstracts the root cause analysis process into signature identification for symptom and diagnostic events, temporal and spatial event correlation, and reasoning and inference logic. G-RCA provides a flexible rule specification language that allows operators to quickly customize G-RCA and provide different root cause analysis tools as new problems need to be investigated. G-RCA is also integrated with data trending, manual data exploration, and statistical correlation mining capabilities. G-RCA has proven to be a highly effective SQM platform in several different applications, and we present results regarding BGP flaps, PIM flaps in Multicast VPN service, and end-to-end throughput degradation in content delivery network (CDN) service.

DDoS defenses based on network capabilities advocate fundamental changes to the Internet. However, despite the many point solutions, there has not been a rigorous study of the entire solution space for capability architectures. We believe the proposed changes to the Internet will inevitably introduce challenges and tradeoffs. To better understand the tradeoffs and identify challenges, we propose a taxonomy to categorize possible options and map the potential solution space. Our taxonomy identifies key components of capability architectures, separates fundamentals from implementation details, and opens up new directions to explore in these architectures.

The era of free IPv4 address allocations has ended and the grey market in IPv4 addresses is now emerging. This paper argues that one cannot and should not try to regulate who sells addresses and at what price, but one does need to provide some proof of ownership in the form of resource certification. In this paper we identify key requirements of resource certification, gained from both theoretical analysis and operational history. We further argue these requirements can be achieved by making use of the existing reverse DNS hierarchy, enhanced with DNS Security. Our analysis compares reverse DNS entries and BGP routing tables and shows this is both feasible and achievable today; an essential requirement as the grey market is also emerging today and solutions are needed now, not years in the future.

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.

As IP networks have become the mainstay of an increasingly diverse set of applications ranging from Internet games and streaming videos, to e-commerce and online-banking, and even to mission-critical 911, best effort service is no longer acceptable. This requires a transformation in network management from detecting and replacing individual faulty network elements to managing the service quality as a whole.

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.

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.

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.

Routing policies play an essential role in how traffic is forwarded across the Internet. The network would not be commercially viable without these routing policies, but policies also introduce inefficiencies and fail to fully exploit the underlying network topology. Our work assumes routes are selected according to some policy such as a valley-free routing policy. However, we apply policy at an aggregate traffic level and don't require individual packets to follow paths that match the policy. Our approach never reduces, and usually increases, the connectivity and capacity of the network, and does not infringe on the underlying motivations that led to the routing policy. By adopting this approach, we also provide polynomial algorithms for otherwise NP-hard problems, including finding maximum policy-observing routing capacity between two sets of ASes, minimizing cuts separating all policy-observing paths between two sets of ASes, and maximizing sets of edge-or vertex-disjoint policy-observing paths.

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.

The DNS Security Extensions (DNSSEC) were developed to add origin authentication and integrity. DNSSEC defined a public key infrastructure over DNS tree hierarchy for the public key validation. In DNSSEC, a parent zone authenticates public keys of its child zones. The authentication hierarchy is broken when a parent does not support DNSSEC. This paper proposes an effective mechanism to overcome this partial deployment problem. Our solution uses a public bulletin board for zones to post their DNSKEY information. Resolvers use posted key information to find key authentication chains that can be used to validate the DNSKEY. Bulletin Board(BB) provides complete trust relationship information when the key authentication hierarchy is broken, and distributes the complete key information even when false zones provide the invalid keys. The bulletin board does not guarantee the correctness of DNSKEY information, but it does guarantee the completeness of the key information. Our approach helps DNS zones to deploy DNSSEC even when their parent zones do not deploy DNSSEC, and it does not require any changes to the current DNSSEC protocol and the existing software.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

Routing protocol faults cause problems ranging from an inability to communicate to excessive routing overhead. This paper proposes a system for detecting a wide range of routing protocol faults. The system deploys virtual routers called RouteMonitors to monitor a routing protocol. We deployed RouteMonitors in the MBone DVMRP infrastructure and uncovered a number of faults. We were also able to identify the cause of these errors and deploy fixes. The result was a substantial improvement in DVMRP route stability. This paper reviews the RouteMonitor approach and details the results achieved in the MBone.