The future of static verification in networking may be obscured by two clouds: the complexity of distributed systems with highly concurrent events, and the decision-making on infrastructures growing without a premeditated plan. This poster discusses a possible solution to these issues, in which the huge space of analyzing distributed systems and the macro-questions of system evolution are addressed by a common structure, a logical implication problem which we call indirect troubleshooting. The usefulness and feasibility of indirect troubleshooting is illustrated by a preliminary realization with the chase, a remarkable process for mechanically deciding implications.

Digital twins have been designed and implemented for diverse applications like smart manufacturing, healthcare, supply chain and retail management. They provide monitoring, remote prognostics and health management capabilities for the various physical assets used in these domains. Many of these capabilities would be beneficial to microservice architectures as well, given the need for lightweight monitoring solutions in multitenant environments. In particular, twins can provide operators with real-time resource usage metrics which help with operational objectives such as resource planning, anomaly detection, rewind and replay and so on. In this work, we propose a design for building digital twins for microservice architectures. As a proof of concept, we focus on modelling the resource utilization as that is a key requirement for monitoring system reliability and security. In general, digital twins require a real world counterpart, a virtual model and a mechanism for consistently keeping both synchronized. We focus on the two latter aspects of the digital twin. Our approach involves converting a formal model of a microservice architecture into a digital twin that can capture and execute an actual cluster's state. We present an extensible architecture connecting the various components of the system and the twin and evaluate the twin's ability to capture the real-time state of a real Kubernetes cluster. We also discuss future extensions which can enhance the system's security by detecting a broad range of attacks.

Digital Twins are evolving as a key component in modern systems with diverse applications like remote prognostics, optimizing run-time operation, anomaly detection, and more. The essential elements of a digital twin are a virtual representation, a physical asset, and the transfer of data/information between the two. IoT deployments are generally characterized by resource constraints, making synchronization of digital twins with IoT devices more challenging. There is a pressing need to optimize the bandwidth of the data transferred between the system and the twin, while ensuring that the twin is able to capture selected key aspects of the current operational state accurately. In this paper, we present TwinSync, a framework that can be utilized to construct flexible real-time representations of deployed IoT systems and efficiently synchronize relevant system states with the twin, over a communication bottleneck, within a configurable application-specific notion of error (henceforth referred to as approximate synchronization). Our approach is optimized to achieve data transfers utilizing less bandwidth without compromising the ability of the twin to replicate real-time system states within the specified approximate synchronization semantics. We evaluate the efficacy of TwinSync's synchronization by conducting both a synthetic analysis and a case study based on a real-life application prototype. Our evaluation indicates that using TwinSync can provide the same or greater accuracy (in many cases) while sending significantly fewer bytes than a bandwidth-insensitive synchronization approach. The result is attributed to a more judicial selection of data to transmit over bottlenecks, compared to bandwidth-insensitive approaches.

The value of database in advancing networking - in the paradigm shift from protocols to software-defined networking - was once highlighted by database-inspired management of network states. Moving beyond factual states, this paper considers semantics management a new frontier in the databases-networking knowledge “transfer”, seeking to manage network policies via structural manipulation of the corresponding software (program). As a proof of concept, we make a case of semantics-based network transformation with the datalog structure and the chase, an elegant process for handling data dependencies (semantics). Our main result is an extension of the classic chase to faure-log; a networking extension of datalog for the richer networking policies.

Traditional network state management focuses on packets that exercise network structures (configurations, procedures) and testify semantics (intentions), but provides little insights into how the structure actually "causes" the semantics. In response to this missed opportunity, we propose reflective networking, which features a network structure capable of altering itself with a causal connection to its semantics. Specifically, we investigate the network datalog structure and the chase, a process that transforms datalog programs by "executing" intents (semantic constraints) that are themselves expressed in datalog. To illustrate the usefulness of reflective networking, this demonstration presents a first use case: we developed an intuitive specification of routing in datalog, and employed the chase to summarize a network's routing behavior by minimizing (repeatedly transforming) the corresponding datalog program.

Ad hoc computing needs at remote locations or locations with insufficient resources due to reasons such as natural disasters require flexible solutions that are readily deployed on demand. We consider one such scenario where unmanned aerial vehicles (UAVs) or drones can be used to provide necessary coverage in terms of computational support. Specifically, we consider an environment where ground-based computational demand is satisfied by aerial drones that share the computational load to provide seamless service. We study transfer and location policies where transfer policy determines whether a job is locally processed by the drone that receives the order and location policy determines where a job is processed if it is sent to another drone. Our results indicate that the mean queue length of jobs waiting to be processed at the drones decreases with sharing the job processing load among the drones in the modeled system. Our results also highlight the beneficial aspects of the two step transfer and location policies.

Recent concepts in defense herald an increasing degree of automation of future military systems, with an emphasis on accelerating sensing-to-decision loops at the tactical edge, reducing their network communication footprint, and improving the inference quality of intelligent components in the loop. These requirements pose resource management challenges, calling for operating-system-like constructs that optimize the use of limited computational resources at the tactical edge. This paper describes these challenges and presents IoBT-OS, an operating system for the Internet of Battlefield Things that aims to optimize decision latency, improve decision accuracy, and reduce corresponding resource demands on computational and network components. A simple case-study with initial evaluation results is shown from a target tracking application scenario.

As Battery Electric Vehicles (BEV) become more popular because of mandates or through organic growth, bottlenecks include the availability of charging facilities and the sheer time it takes to fully charge these vehicles. BEV rental agencies face the additional burden to decide on the number of vehicles to fully charge and ready to go for the next day. We develop a stochastic model to help facilitate this process. Specifically, we develop expressions for the number of additional vehicles to charge based on Uniform demand, accessible charging facilities, and the available number of partially charged vehicles.

Modern "self-driving'' service infrastructures consist of a diverse collection of distributed control components providing a broad spectrum of application- and network-centric functions. The complex and non-deterministic nature of these interactions leads to failures, ranging from subtle gray failures to catastrophic service outages, that are difficult to anticipate and repair.

In the aftermath of a disaster, the ability to reliably communicate and coordinate emergency response could make a meaningful difference in the number of lives saved or lost. However, post-disaster areas tend to have limited functioning communication network infrastructure while emergency response teams are carrying increasingly more devices, such as sensors and video transmitting equipment, which can be low-powered with limited transmission ranges. In such scenarios, unmanned aerial vehicles (UAVs) can be used as relays to connect these devices with each other. Since first responders are likely to be constantly mobile, the problem of where these UAVs are placed and how they move in response to the changing environment could have a large effect on the number of connections this UAV relay network is able to maintain. In this work, we propose DroneDR, a reinforcement learning framework for UAV positioning that uses information about connectivity requirements and user node positions to decide how to move each UAV in the network while maintaining connectivity between UAVs. The proposed approach is shown to outperform other greedy heuristics across a broad range of scenarios and demonstrates the potential in using reinforcement learning techniques to aid communication during disaster relief operations.

Typosquatting is a blackhat practice that relies on human error and low-cost domain registrations to hijack legitimate traffic from well-established websites. The technique is typically used for phishing, driving traffic towards competitors or disseminating indecent or malicious content and as such remains a concern for businesses. We take a fresh new look at this well-studied phenomenon to explore why some URLs are more vulnerable to typing mistakes than others. We explore the relationship between human hand anatomy, keyboard layouts and typing mistakes using various URL datasets. We create an extensive user-centric typographical model and compute a Hardness Quotient (likelihood of mistyping) for each URL using a quantitative measure for finger and hand effort. Furthermore, our model predicts the most likely typos for each URL which can then be defensively registered. Cross-validation against actual URL and DNS datasets suggests that this is a meaningful and effective defense mechanism.

Recent years have seen significant advancement in the field of formal network verification. Tools have been proposed for offline data plane verification, real-time data plane verification and configuration verification under arbitrary, but static sets of failures. However, due to the fundamental limitation of not treating the network as an evolving system, current verification platforms have significant constraints in terms of scope. In real-world networks, correctness policies may be violated only through a particular combination of environment events and protocol actions, possibly in a non-deterministic sequence. Moreover, correctness specifications themselves may often correlate multiple data plane states, particularly when dynamic data plane elements are present. Tools in existence today are not capable of reasoning about all the possible network events, and all the subsequent execution paths that are enabled by those events. We propose Plankton, a verification platform for identifying undesirable evolutions of networks. By combining symbolic modeling of data plane and control plane with explicit state exploration, Plankton performs a goal-directed search on a finite-state transition system that captures the behavior of the network as well as the various events that can influence it. In this way, Plankton can automatically find policy violations that can occur due to a sequence of network events, starting from the current state. Initial experiments have successfully predicted scenarios like BGP Wedgies.

The vast attack surface of clouds presents a challenge in deploying scalable and effective defenses. Traditional security mechanisms, which work from inside the VM fail to provide strong protection as attackers can bypass them easily. The only available option is to provide security from the layer below the VM i.e., the hypervisor. Previous works that attempt to secure VMs from "outside" either incur substantial space or compute overheads making them slow and impractical or require modifications to the OS or the application codebase. To address these issues, we propose an anomaly detection fabric for clouds based on system call monitoring, which compresses the stream of system calls at their source making the system scalable and near real-time. Our system requires no modifications to the guest OS or the application making it ideal for the data center setting. Additionally, for robust and early detection of threats, we leverage the notion of VM/container communities that share information about attacks in their early stages to provide immunity to the entire deployment. We make certain aspects of the system flexible so that vendors can tune metrics to offer customized protection to clients based on their workload types. Detailed evaluation on a prototype implementation on KVM substantiates our claims.

Open communications over the Internet pose serious threats to countries with repressive regimes, leading them to develop and deploy censorship mechanisms within their networks. Unfortunately, existing censorship circumvention systems do not provide high availability guarantees to their users, as censors can easily identify, hence disrupt, the traffic belonging to these systems using today's advanced censorship technologies. In this paper, we propose Serving the Web by Exploiting Email Tunnels (SWEET), a highly available censorship-resistant infrastructure. SWEET works by encapsulating a censored user's traffic inside email messages that are carried over public email services like Gmail and Yahoo Mail. As the operation of SWEET is not bound to any specific email provider, we argue that a censor will need to block email communications all together in order to disrupt SWEET, which is unlikely as email constitutes an important part of today's Internet. Through experiments with a prototype of our system, we find that SWEET's performance is sufficient for Web browsing. In particular, regular Websites are downloaded within couple of seconds.

With the advent of big data, modern businesses face an increasing need to store and process large volumes of sensitive customer information on the cloud. In these environments, resources are shared across a multitude of mutually untrusting tenants increasing propensity for data leakage. This problem stands to grow further in severity with increasing use of clouds in all aspects of our daily lives and the recent spate of high-profile data exfiltration attacks are evidence. To highlight this serious issue, we present a novel and highspeed network-based covert channel that is robust and circumvents a broad set of security mechanisms currently deployed by cloud vendors. We successfully test our channel on numerous network environments, including commercial clouds such as EC2 and Azure. Using an information theoretic model of the channel, we derive an upper bound on the maximum information rate and propose an optimal coding scheme. Our adaptive decoding algorithm caters to the cross traffic in the channel and maintains high bit rates and extremely low error rates. Finally, we discuss several effective avenues for mitigation of the aforementioned channel and provide insights into how data exfiltration can be prevented in such shared environments.

Abstract Many governments block their citizens’ access to much of the Internet. Simple workarounds are unreliable; censors quickly discover and patch them. Previously proposed robust approaches either have non-trivial obstacles to deployment, or rely on low-performance covert channels that cannot support typical Internet usage such as streaming video. We present Salmon, an incrementally deployable system designed to resist a censor with the resources of the “Great Firewall” of China. Salmon relies on a network of volunteers in uncensored countries to run proxy servers. Although any member of the public can become a user, Salmon protects the bulk of its servers from being discovered and blocked by the censor via an algorithm for quickly identifying malicious users. The algorithm entails identifying some users as especially trustworthy or suspicious, based on their actions. We impede Sybil attacks by requiring either an unobtrusive check of a social network account, or a referral from a trustworthy user.

Conjoinment of emulation and simulation in virtual time requires that emulated execution bursts be ascribed a duration in virtual time, and that emulated execution and simulation executions be coordinated within this common virtual time basis. This paper shows how an open source tool TimeKeeper for coordinating emulations in virtual time can be integrated with three different existing software emulations/simulations: CORE, ns-3, and S3F. We describe for each of these the modifications made to the tools to support this integration, and examine experiments designed to assess the accuracy of the combined models. Timekeeper permits much tighter sychronization emulation and simulation than has ever been achieved before.

To reduce the impact of network congestion on big data jobs, cluster management frameworks use various heuristics to schedule compute tasks and/or network flows. Most of these schedulers consider the job input data fixed and greedily schedule the tasks and flows that are ready to run. However, a large fraction of production jobs are recurring with predictable characteristics, which allows us to plan ahead for them. Coordinating the placement of data and tasks of these jobs allows for significantly improving their network locality and freeing up bandwidth, which can be used by other jobs running on the cluster. With this intuition, we develop Corral, a scheduling framework that uses characteristics of future workloads to determine an offline schedule which (i) jointly places data and compute to achieve better data locality, and (ii) isolates jobs both spatially (by scheduling them in different parts of the cluster) and temporally, improving their performance. We implement Corral on Apache Yarn, and evaluate it on a 210 machine cluster using production workloads. Compared to Yarn's capacity scheduler, Corral reduces the makespan of these workloads up to 33% and the median completion time up to 56%, with 20-90% reduction in data transferred across racks.

Abstract The Tor anonymity network has been shown vulnerable to traffic analysis attacks by autonomous systems (ASes) and Internet exchanges (IXes), which can observe different overlay hops belonging to the same circuit. We evaluate whether network path prediction techniques provide an accurate picture of the threat from such adversaries, and whether they can be used to avoid this threat. We perform a measurement study by collecting 17.2 million traceroutes from Tor relays to destinations around the Internet. We compare the collected traceroute paths to predicted paths using state-of-the-art path inference techniques. We find that traceroutes present a very different picture, with the set of ASes seen in the traceroute path differing from the predicted path 80% of the time. We also consider the impact that prediction errors have on Tor security. Using a simulator to choose paths over a week, our traceroutes indicate a user has nearly a 100% chance of at least one compromise in a week with 11% of total paths containing an AS compromise and less than 1% containing an IX compromise when using default Tor selection. We find modifying the path selection to choose paths predicted to be safe lowers total paths with an AS compromise to 0.14% but still presents a 5–11% chance of at least one compromise in a week while making 5% of paths fail, with 96% of failures due to false positives in path inferences. Our results demonstrate more measurement and better path prediction is necessary to mitigate the risk of AS and IX adversaries to Tor.

Route instability is an important contributor to data plane unreliability on the Internet and also incurs load on the control plane of routers. In this paper, we study how route selection schemes can avoid these changes in routes. Modifying route selection implies a tradeoff between stability, deviation from operators' preferred routes, and availability of routes. We develop algorithms to lower-bound the feasible points in these tradeoff spaces. We also propose a new approach, Stable Route Selection (SRS), which uses flexibility in route selection to improve stability without sacrificing availability and with a controlled amount of deviation. Through large-scale simulation, a software-router implementation, and an emulation with real-world BGP update feeds, we demonstrate that SRS is a promising approach to safely stabilize route selection.

The widespread use of smart devices gives rise to privacy concerns. Fingerprinting smart devices can jeopardize privacy by allowing remote identification without user awareness. We study the feasibility of using microphones and speakers embedded in smartphones to uniquely fingerprint individual devices. During fabrication, subtle imperfections arise in device microphones and speakers, which induce anomalies in produced and received sounds. We exploit this observation to fingerprint smartphones through playback and recording of audio samples. We explore different acoustic features and analyze their ability to successfully fingerprint smartphones. Our experiments show that not only is it possible to fingerprint devices manufactured by different vendors but also devices that have the same maker and model; on average we were able to accurately attribute 98% of all recorded audio clips from 50 different Android smartphones. Our study also identifies the prominent acoustic features capable of fingerprinting smart devices with a high success rate, and examines the effect of background noise and other variables on fingerprinting accuracy.

To conceal user identities, Tor, a popular anonymity system, forwards traffic through multiple relays. These relays, however, are often unreliable, leading to a degraded user experience. Worse yet, malicious relays may strategically introduce deliberate failures to increase their chance of compromising anonymity. In this paper we propose a reputation system that profiles the reliability of relays in an anonymity system based on users' past experience. A particular challenge is that an observed failure in an anonymous communication cannot be uniquely attributed to a single relay. This enables an attack where malicious relays can target a set of honest relays in order to drive down their reputation. Our system defends against this attack in two ways. Firstly, we use an adaptive exponentially-weighted moving average (EWMA) that ensures malicious relays adopting time-varying strategic behavior obtain low reputation scores over time. Secondly, we propose a filtering scheme based on the evaluated reputation score that can effectively discard relays involved in such attacks. We use probabilistic analysis, simulations, and real-world experiments to validate our reputation system. We show that the dominant strategy for an attacker is to not perform deliberate failures, but rather maintain a high quality of service. Our reputation system also significantly improves the reliability of path construction even in the absence of attacks. Finally, we show that the benefits of our reputation system can be realized with a moderate number of observations, making it feasible for individual clients to perform their own profiling, rather than relying on an external entity.

Increasingly, datacenters are virtualized and software-defined. Live virtual machine (VM) migration is becoming an indispensable management tool in such environments. However, VMs often have a tight coupling with the underlying network. Hence, cloud providers are beginning to offer tenants more control over their virtual networks. Seamless migration of all (or part) of a virtual network greatly simplifies management tasks like planned maintenance, optimizing resource usage, and cloud bursting. Our LIME architecture efficiently migrates an ensemble, a collection of virtual machines and virtual switches, for any arbitrary controller and end-host applications. To minimize performance disruptions, during the migration, LIME temporarily runs all or part of a virtual switch on multiple physical switches. Running a virtual switch on multiple physical switches must be done carefully to avoid compromising application correctness. To that end, LIME merges events, combines traffic statistics, and preserves consistency among multiple physical switches even across changes to the packet-handling rules. Using a formal model, we prove that migration under LIME is transparent to applications, i.e., any execution of the controller and end-host applications during migration is a completely valid execution that could have taken place in a migration-free setting. Experiments with our prototype, built on the Floodlight controller, show that ensemble migration can be an efficient tool for network management.

We present TimeKeeper: a simple lightweight approach to embedding Linux containers (LXC) in virtual time. Each container can be directed to progress in virtual time either more rapidly or more slowly than the physical wall clock time. As a result, interactions between an LXC and physical devices can be artificially scaled, e.g., to make a network appear to be ten times faster with respect to the software within the LXC than it actually is. Our approach also supports synchronized (in virtual time) emulation, by grouping LXCs together into an experiment where the virtual times of containers are kept synchronized, even when they advance at different speeds. This has direct application to the integration of emulation and simulation within a common framework.

Live virtual machine (VM) migration can move applications from one location to another without a disruption in service. However, applications often consist of multiple VMs and rely on the state of the underlying network for basic reachability, access control, and QoS functionality. Rather than migrating an individual VM, we show how to migrate an ensemble---the VMs, the network, and the management system---to a different set of physical resources. Our LIME (LIve Migration of Ensembles) design leverages recent advances in Software Defined Networking (SDN) for a clear separation between the controller and the data-plane state in the switches. Transparent to the application running on the controller, LIME clones the data-plane state to a new set of switches, and then incrementally migrates the traffic sources (e.g., the VMs). During this transition, both networks deliver traffic and LIME maintains synchronized state. Experiments with our initial prototype, built on the Floodlight OpenFlow controller, suggest that network migration does not have to be a disruptive, middle-of-the-night maintenance event, but can become an integral network management mechanism completely transparent to applications.

Operational network data, management data such as customer care call logs and equipment system logs, is a very important source of information for network operators to detect problems in their networks. Unfortunately, there is lack of efficient tools to automatically track and detect anomalous events on operational data, causing ISP operators to rely on manual inspection of this data. While anomaly detection has been widely studied in the context of network data, operational data presents several new challenges, including the volatility and sparseness of data, and the need to perform fast detection (complicating application of schemes that require offline processing or large/stable data sets to converge). To address these challenges, we propose Tiresias, an automated approach to locating anomalous events on hierarchical operational data. Tiresias leverages the hierarchical structure of operational data to identify high-impact aggregates (e.g., locations in the network, failure modes) likely to be associated with anomalous events. To accommodate different kinds of operational network data, Tiresias consists of an online detection algorithm with low time and space complexity, while preserving high detection accuracy. We present results from two case studies using operational data collected at a large commercial IP network operated by a Tier-1 ISP: customer care call logs and set-top box crash logs. By comparing with a reference set verified by the ISP's operational group, we validate that Tiresias can achieve >;94% accuracy in locating anomalies. Tiresias also discovered several previously unknown anomalies in the ISP's customer care cases, demonstrating its effectiveness.

Today's data centers face extreme challenges in providing low latency. However, fair sharing, a principle commonly adopted in current congestion control protocols, is far from optimal for satisfying latency requirements.

The memory Internet routers use to store paths to destinations is expensive, andmustbecontinuallyupgradedinthefaceofsteadilyincreasingrouting table size. Unfortunately, routing protocols are not designed to gracefully handle cases where memory becomes full, which arises increasingly often due to misconfigurations and routing table growth. Hence router memory must typically be heavily overprovisioned by network operators, inflating operating costs and administrative effort. The research community has primarily focused on clean-slate solutions that cannot interoperate with the deployed base of protocols. This paper presents an incrementally-deployable Memory Management System (MMS) that reduces associated router state by up to 70%. The MMS coalesces prefixes to reduce memory consumption and can be deployed locally on each router or centrally on a route server. The system can operate transparently, without requiring changes in other ASes. Our memory manager can extend router lifetimes up to seven years, given current prefix growth trends. 1.

The ability to forward packets on the Internet is highly intertwined with the availability and robustness of the Domain Name System (DNS) infrastructure. Unfortunately, the DNS suffers from a wide variety of problems arising from implementation errors, including vulnerabilities, bogus queries, and proneness to attack. In this work, we present a preliminary design and early prototype implementation of a system that leverages diversified replication to increase tolerance of DNS to implementation errors. Our design leverages software diversity by running multiple redundant copies of software in parallel, and leverages data diversity by sending redundant requests to multiple servers. Using traces of DNS queries, we demonstrate our design can keep up with the loads of a large university's DNS traffic, while improving resilience of DNS.

Many users face surveillance of their Internet communications and a significant fraction suffer from outright blocking of certain destinations. Anonymous communication systems allow users to conceal the destinations they communicate with, but do not hide the fact that the users are using them. The mere use of such systems may invite suspicion, or access to them may be blocked. We therefore propose Cirripede, a system that can be used for unobservable communication with Internet destinations. Cirripede is designed to be deployed by ISPs; it intercepts connections from clients to innocent-looking destinations and redirects them to the true destination requested by the client. The communication is encoded in a way that is indistinguishable from normal communications to anyone without the master secret key, while public-key cryptography is used to eliminate the need for any secret information that must be shared with Cirripede users.

Anonymity systems such as Tor aim to enable users to communicate in a manner that is untraceable by adversaries that control a small number of machines. To provide efficient service to users, these anonymity systems make full use of forwarding capacity when sending traffic between intermediate relays. In this paper, we show that doing this leaks information about the set of Tor relays in a circuit (path). We present attacks that, with high confidence and based solely on throughput information, can (a) reduce the attacker's uncertainty about the bottleneck relay of any Tor circuit whose throughput can be observed, (b) exactly identify the guard relay(s) of a Tor user when circuit throughput can be observed over multiple connections, and (c) identify whether two concurrent TCP connections belong to the same Tor user, breaking unlinkability. Our attacks are stealthy, and cannot be readily detected by a user or by Tor relays. We validate our attacks using experiments over the live Tor network. We find that the attacker can substantially reduce the entropy of a bottleneck relay distribution of a Tor circuit whose throughput can be observed-the entropy gets reduced by a factor of 2 in the median case. Such information leaks from a single Tor circuit can be combined over multiple connections to exactly identify a user's guard relay(s). Finally, we are also able to link two connections from the same initiator with a crossover error rate of less than 1.5% in under 5 minutes. Our attacks are also more accurate and require fewer resources than previous attacks on Tor.

For interactive networked applications like web browsing, every round-trip time (RTT) matters. We introduce ASAP, a new naming and transport protocol that reduces latency by shortcutting DNS requests and eliminating TCP's three-way handshake, while ensuring the key security property of verifiable provenance of client requests. ASAP eliminates between one and two RTTs, cutting the delay of small requests by up to two-thirds.

In this paper, we propose countermeasures to mitigate damage caused by spoofing attacks in Delay-Tolerant Networks (DTNs). In our model, an attacker spoofs someone else's address (the victim's) to absorb packets from the network intended for that victim. Address spoofing is arguably a very severe attack in DTNs, compared to other known attacks, such as dropping packets. Without a Public Key Infrastructure in DTNs, providing protection against this attack is challenging. We propose SPREAD (countermeasure against SPoofing by REplica ADjustment), a solution that assesses evidence of spoofing and offers countermeasures designed for quota-based multi-copy routing protocols. Our solution relies on reducing the weight of packet copies, charged to the routing quota, when these packets are given to a node suspected of spoofing. The weight reduction increases as spoofing evidence mounts against a node. The approach is designed to probabilistically maintain the same number of packet copies in the network as would be the case in the absence of attacks, despite the actual occurrence of spoofing. We show that SPREAD makes DTNs robust against spoofing attacks, does not overburden the network, and limits the overall overhead within a certain bound.

For interactive networked applications like web browsing, every round-trip time (RTT) matters. We introduce ASAP, a new naming and transport protocol that reduces latency by shortcutting DNS requests and eliminating TCP's three-way handshake, while ensuring the key security property of verifiable provenance of client requests. ASAP eliminates between one and two RTTs, cutting the delay of small requests by up to two-thirds.

Diagnosing problems in networks is a time-consuming and error-prone process. Existing tools to assist operators primarily focus on analyzing control plane configuration. Configuration analysis is limited in that it cannot find bugs in router software, and is harder to generalize across protocols since it must model complex configuration languages and dynamic protocol behavior.

Source-controlled routing has been proposed as a way to improve flexibility of future network architectures, as well as simplifying the data plane. However, if a packet specifies its path, this precludes fast local re-routing within the network. We propose SlickPackets, a novel solution that allows packets to slip around failures by specifying alternate paths in their headers, in the form of compactly-encoded directed acyclic graphs. We show that this can be accomplished with reasonably small packet headers for real network topologies, and results in responsiveness to failures that is competitive with past approaches that require much more state within the network. Our approach thus enables fast failure response while preserving the benefits of source-controlled routing.

IP networks today require massive effort to configure and manage. Ethernet is vastly simpler to manage, but does not scale beyond small local area networks. This article describes an alternative network architecture called SEATTLE that achieves the best of both worlds: The scalability of IP combined with the simplicity of Ethernet. SEATTLE provides plug-and-play functionality via flat addressing, while ensuring scalability and efficiency through shortest-path routing and hash-based resolution of host information. In contrast to previous work on identity-based routing, SEATTLE ensures path predictability, controllability, and stability, thus simplifying key network-management operations, such as capacity planning, traffic engineering, and troubleshooting. We performed a simulation study driven by real-world traffic traces and network topologies, and used Emulab to evaluate a prototype of our design based on the Click and XORP open-source routing platforms. Our experiments show that SEATTLE efficiently handles network failures and host mobility, while reducing control overhead and state requirements by roughly two orders of magnitude compared with Ethernet bridging.

Policy autonomy exercised by Autonomous Systems (ASes) on the Internet can result in persistent oscillations in Border Gateway Protocol, the Internet's inter-domain routing protocol. Current solutions either rely on globally consistent policy assignments, or require significant deviations from locally assigned policies, resulting in significant loss of autonomy of ASes. In this paper, we take a different approach that guarantees stability with less restrictive policies. Namely, we propose multipath routing to find a better trade-off between AS policy autonomy and system stability. We design an algorithm, STABLE PATH(S) ASSIGNMENT (SPA), that provably detects persistent oscillations and eliminates these oscillations by assigning multiple paths to some ASes in the network. Such an assignment allows each AS to use its most-preferred available path, while requiring very few ASes to carry transit traffic along additional paths in order to break oscillations. We design a distributed protocol for SPA and present tight bounds on the number of paths assigned to the ASes in the network. Using simulations on the AS graph, we show that in presence of oscillations, SPA assigns at most two paths to any AS in the network (in 99.9% of the instances), with an extremely small fraction of ASes assigned the extra path.

Software bugs in routers lead to network outages, security vulnerabilities, and other unexpected behavior. Rather than simply crashing the router, bugs can violate protocol semantics, rendering traditional failure detection and recovery techniques ineffective. Handling router bugs is an increasingly important problem as new applications demand higher availability, and networks become better at dealing with traditional failures. In this paper, we tailor software and data diversity (SDD) to the unique properties of routing protocols, so as to avoid buggy behavior at run time. Our bug-tolerant router executes multiple diverse instances of routing software, and uses voting to determine the output to publish to the forwarding table, or to advertise to neighbors. We design and implement a router hypervisor that makes this parallelism transparent to other routers, handles fault detection and booting of new router instances, and performs voting in the presence of routing-protocol dynamics, without needing to modify software of the diverse instances. Experiments with BGP message traces and open-source software running on our Linux-based router hypervisor demonstrate that our solution scales to large networks and efficiently masks buggy behavior.

Multichannel wireless networks provide the flexibility to utilize the available spectrum efficiently for achieving improved system performance in terms of throughput and spectral efficiency. However, there has been no practical means for provisioning quality of service (QoS) in multichannel wireless networks. While previous proposals providing signaling and adaptation mechanisms for QoS, they support only fixed-width channels, restricting system performance in networks supporting variable-width channels. In this paper, we propose a distributed mechanism for provisioning QoS by adapting the channel widths in a multichannel, ad-hoc network. Our algorithm builds upon the well-known ETT routing metric to incorporate bandwidth adaptability. We also propose mechanisms for performing admission control and congestion control jointly in a multihop setting. We demonstrate the performance of our algorithm using a modified AODV routing protocol through extensive simulations. Our simulations results show that our proposed approach can achieve up to twice the spectral efficiency and data rates when compared to the greedy approach. Furthermore, our results show that our proposed approach scales well as the network density increases.

Routing protocols are implemented in the form of software running on a general-purpose microprocessor. However, conventional software-based router architectures face significant scaling challenges in the presence of ever-increasing routing table growth and churn. Recent advances in programmable hardware and high-level hardware description languages provide the opportunity to implement BGP directly at the hardware layer. Hardware-based implementation allows designs to take advantage of the parallelization and customizability of the underlying hardware to improve performance. As a first step in this direction, we design and implement a hardware-based BGP architecture. To understand the challenges in doing this, we propose an architecture and logical design for the core components of BGP running as a logical circuit in an FPGA. We then enumerate sources of complexity and performance bottlenecks, and derive modifications to BGP that reduce complexity of hardware offloading. Our results based on update traces from core Internet routers indicate an order of magnitude improvement in processing time and throughput.

IP networks today require massive effort to configure and manage. Ethernet is vastly simpler to manage, but does not scale beyond small local area networks. This paper describes an alternative network architecture called SEATTLE that achieves the best of both worlds: The scalability of IP combined with the simplicity of Ethernet. SEATTLE provides plug-and-play functionality via flat addressing, while ensuring scalability and efficiency through shortest-path routing and hash-based resolution of host information. In contrast to previous work on identity-based routing, SEATTLE ensures path predictability and stability, and simplifies network management. We performed a simulation study driven by real-world traffic traces and network topologies, and used Emulab to evaluate a prototype of our design based on the Click and XORP open-source routing platforms. Our experiments show that SEATTLE efficiently handles network failures and host mobility, while reducing control overhead and state requirements by roughly two orders of magnitude compared with Ethernet bridging.

Current distributed routing paradigms (such as link-state, distance-vector, and path-vector) involve a convergence process consisting of an iterative exploration of intermediate routes triggered by certain events such as link failures. The convergence process increases router load, introduces outages and transient loops, and slows reaction to failures. We propose a new routing paradigm where the goal is not to reduce the convergence times but rather to eliminate the convergence process completely. To this end, we propose a technique called Failure-Carrying Packets (FCP) that allows data packets to autonomously discover a working path without requiring completely up-to-date state in routers. Our simulations, performed using real-world failure traces and Rocketfuel topologies, show that: (a) the overhead of FCP is very low, (b) unlike traditional link-state routing (such as OSPF), FCP can provide both low loss-rate as well as low control overhead, (c) compared to prior work in backup path pre-computations, FCP provides better routing guarantees under failures despite maintaining lesser state at the routers.

It is accepted wisdom that the current Internet architecture conflates network locations and host identities, but there is no agreement on how a future architecture should distinguish the two. One could sidestep this quandary by routing directly on host identities themselves, and eliminating the need for network-layer protocols to include any mention of network location. The key to achieving this is the ability to route on flat labels. In this paper we take an initial stab at this challenge, proposing and analyzing our ROFL routing algorithm. While its scaling and efficiency properties are far from ideal, our results suggest that the idea of routing on flat labels cannot be immediately dismissed.

This paper presents Virtual Ring Routing (VRR), a new network routing protocol that occupies a unique point in the design space. VRR is inspired by overlay routing algorithms in Distributed Hash Tables (DHTs) but it does not rely on an underlying network routing protocol. It is implemented directly on top of the link layer. VRR provides both raditional point-to-point network routing and DHT routing to the node responsible for a hash table key.VRR can be used with any link layer technology but this paper describes a design and several implementations of VRR that are tuned for wireless networks. We evaluate the performance of VRR using simulations and measurements from a sensor network and an 802.11a testbed. The experimental results show that VRR provides robust performance across a wide range of environments and workloads. It performs comparably to, or better than, the best wireless routing protocol in each experiment. VRR performs well because of its unique features: it does not require network flooding or trans-lation between fixed identifiers and location-dependent addresses.

It is well-known that BGP, the current inter-domain routing protocol, has many deficiencies. This paper describes a hybrid link-state and path-vector protocol called HLP as an alternative to BGP that has vastly better scalability, isolation and convergence properties. Using current BGP routing information, we show that HLP, in comparison to BGP, can reduce the churn-rate of route updates by a factor 400 as well as isolate the effect of routing events to a region 100 times smaller than that of BGP. For a majority of Internet routes, HLP guarantees worst-case linear-time convergence. We also describe a prototype implementation of HLP on top of the XORP router platform. HLP is not intended to be a finished and final proposal for a replacement for BGP, but is instead offered as a starting point for debates about the nature of the next-generation inter-domain routing protocol.

This paper we present a comparative study of a few simple but representative usage-based pricing strategies. For the current best-effort Internet, we introduce a QoS sensitive pricing mechanism which takes into account the fact that the quality of received audio degrades as the number of hops traversed by the audio packets increases. We compare the QoS sensitive pricing with flat pricing, congestion sensitive pricing, and a hybrid scheme that combines QoS sensitive and congestion sensitive pricing schemes. Our study is based on a two class user model; type 1 users pay any price for the best QoS and type 2 users request the best QoS at a cost that is less than some maximum price they are willing to pay. Experimental results show the following: i) The QoS sensitive pricing has the lowest blocking probability and also the lowest service distance (the average distance between the client and the servicing gateway) for type 1 calls of any of the schemes. However, it does so by forcing type 2 calls away from the home gateway and hence gives a lower QoS to these calls. ii) The congestion sensitive pricing scheme adapts to the current load at a gateway and hence is good at providing a low service distance to type 2 calls. Unfortunately, it does this by increasing the blocking probability of a type 2 call. iii) The combination of congestion sensitive and QoS sensitive pricing is quite effective and incorporates the best elements of both schemes: it has a very low blocking probability (close to that of QoS sensitive pricing) while retaining a low service distance of type 2 calls. However, at very high loads, the correlation between price and distance breaks down resulting in an increase in the service distance of type 1 calls.