Proposed Bell pair swapping protocols, an essential component of the Quantum Internet, are planned-path: specific structured routing paths are reserved prior to the execution of the swapping process. This makes sense when one assumes the state used in the swapping process is expensive, fragile, and unstable. However, lessons from classical networking have shown that while reservations seem promising in concept, flexible, reservation-light or free approaches often outperform their more restrictive counterparts in well-provisioned networks. In this paper, we propose that a path-oblivious approach is more amenable to supporting swapping as quantum state evolves into a cheaper, more robust form. We formulate the swapping process as a linear program and present and evaluate a fairly naive baseline swapping protocol that tries to balance Bell pairs throughout the network. Preliminary results show that while naive balancing leaves room for improvement, investigating path-oblivious swapping is a promising direction.

Interactive visualization interfaces enable users to efficiently explore, analyze, and make sense of their datasets. However, as data grows in size, it becomes increasingly challenging to build data interfaces that meet the interface designer's desired latency expectations and resource constraints. Cloud DBMSs, while optimized for scalability, often fail to meet latency expectations, necessitating complex, bespoke query execution and optimization techniques for data interfaces. This involves manually navigating a huge optimization space that is sensitive to interface design and resource constraints, such as client vs server data and compute placement, choosing which computations are done offline vs online, and selecting from a large library of visualization-optimized data structures. This paper advocates for a Physical Visualization Design (PVD) tool that decouples interface design from system design to provide design independence. Given an interfaces underlying data flow, interactions with latency expectations, and resource constraints, PVD checks if the interface is feasible and, if so, proposes and instantiates a middleware architecture spanning the client, server, and cloud DBMS that meets the expectations. To this end, this paper presents Jade, the first prototype PVD tool that enables design independence. Jade proposes an intermediate representation called Diffplans to represent the data flows, develops cost estimation models that trade off between latency guarantees and plan feasibility, and implements an optimization framework to search for the middleware architecture that meets the guarantees. We evaluate Jade on six representative data interfaces as compared to Mosaic and Azure SQL database. We find Jade supports a wider range of interfaces, makes better use of available resources, and can meet a wider range of data, latency, and resource conditions.

Network verification, broadly defined as proving the correctness of certain properties resulting from a network's configuration, cannot be efficiently solved on classical hardware via brute force. Prior work has developed a variety of methods that scale by observing a structure in the search space and then evaluating classes induced by that structure. However, even these classification mechanisms have their limitations. In this paper, we consider a radically different approach: applying quantum computing to more efficiently solve network verification problems. We provide an overview of how to map variants of verification problems into unstructured search problems that can be solved via quantum computing with quadratic speedup, making the approach feasible in theory to problems that twice as big in the size of the input. Emerging quantum systems cannot yet tackle problems of practical interest, but rapid advances in hardware and algorithm development make now a great time to start thinking about their application. With this in mind, we explore the limits of scale of the problem for which quantum computing can solve network verification problems as unstructured search.

Bloom Filters are a space-efficient data structure used for the testing of membership in a set that errs only in the False Positive direction. However, the standard analysis that measures this False Positive rate provides a form of worst case bound that is both overly conservative for the majority of network applications that utilize Bloom Filters, and reduces accuracy by not taking into account the actual state (number of bits set) of the Bloom Filter after each arrival. In this paper, we more accurately characterize the False Positive dynamics of Bloom Filters as they are commonly used in networking applications. In particular, network applications often utilize a Bloom Filter that “recycles”: it repeatedly fills, and upon reaching a certain level of saturation, empties and fills again. In this context, it makes more sense to evaluate performance using the average False Positive rate instead of the worst case bound. We show how to efficiently compute the average False Positive rate of recycling Bloom Filter variants via renewal and Markov models. We apply our models to both the standard Bloom Filter and a "two-phase" variant, verify the accuracy of our model with simulations, and find that the previous analysis’ worst-case formulation leads to up to a 30% reduction in the efficiency of Bloom Filter when applied in network applications, while two-phase overhead diminishes as the needed False Positive rate is tightened.

Serverless computing is an attractive cloud services paradigm, simultaneously promising reduced cost and greater flexibility for customers and increased revenues and higher resource utilization for cloud providers. In this paper, we present an analysis of the potential cost benefits of serverless computing for end customers and cloud providers. Using realistic cost models, queueing theoretic performance models, and a game theoretic formulation, we explore the tradeoffs between serverless computing (SC) and traditional cloud computing (virtual machine, VM). In the proposed framework, customers distribute their workload between SC and VM to minimize their cost while maintaining a particular performance constraint, while the cloud provider sets SC and VM prices to maximize its profit. We explore the impact of relative prices, customer workload, service capacity, and provider costs. Our main result is the identification and characterization of three optimal operational regimes for both customers and the provider that leverage either SC or VM only, or both, in a hybrid configuration. The various insights provided in this paper can help both cloud providers and customers better understand the tradeoffs and implications of a hybrid system that combines serverless and VM rental with corresponding pricing models.

WiFi is the dominant means for home Internet access, yet is frequently a performance bottleneck. Without reliable, satisfactory performance at the last hop, end-to-end quality of service (QoS) efforts will fail. Three major reasons for WiFi bottlenecking performance are its: 1) inherent wireless channel characteristics, 2) approach to access control of the shared broadcast channel, and 3) impact on transport layer protocols, such as TCP, that operate end-to-end, and over-react to the loss or delay caused by the single WiFi link. In this paper, we leverage the philosophy of centralization in modern networking and present our cross layer design to address the problem. Specifically, we introduce centralized control at the point of entry/egress into the WiFi network. Based on network conditions measured from buffer sizes, airtime and throughput, flows are scheduled to the optimal utility. Unlike most existing WiFi QoS approaches, our design only relies on transparent modifications, requiring no changes to the network (including link layer) protocols, applications, or user intervention. Through extensive experimental investigation, we show that our design significantly enhances the reliability and predictability of WiFi performance, providing a “virtual wire”-like link to the targeted application.

Wireless object tracking applications are gaining popularity and will soon utilize emerging ultra-low-power device-to-device communication. However, severe energy constraints require much more careful accounting of energy usage than what prior art provides. In particular, the available energy, the differing power consumption levels for listening, receiving, and transmitting, as well as the limited control bandwidth must all be considered. Therefore, we formulate the problem of maximizing the throughput among a set of heterogeneous broadcasting nodes with differing power consumption levels, each subject to a strict ultra-low-power budget. We obtain the oracle throughput (i.e., maximum throughput achieved by an oracle) and use Lagrangian methods to design EconCast - a simple asynchronous distributed protocol in which nodes transition between sleep, listen, and transmit states, and dynamically change the transition rates. We also show that EconCast approaches the oracle throughput. The performance is evaluated numerically and via extensive simulations and it is shown that EconCast outperforms prior art by 6x - 17x under realistic assumptions. Finally, we implement EconCast using the TI eZ430-RF2500-SEH energy harvesting nodes and experimentally show that in realistic environments it obtains 57% - 77% of the achievable throughput.

Object tracking applications are gaining popularity and will soon utilize Energy Harvesting (EH) low-power nodes that will consume power mostly for Neighbor Discovery (ND) (i.e., identifying nodes within communication range). Although ND protocols were developed for sensor networks, the challenges posed by emerging EH low-power transceivers were not addressed. Therefore, we design an ND protocol tailored for the characteristics of a representative EH prototype: the TI eZ430-RF2500-SEH. We present a generalized model of ND accounting for unique prototype characteristics (i.e., energy costs for transmission/reception, and transceiver state switching times/costs). Then, we present the Power Aware Neighbor Discovery Asynchronously (Panda) protocol in which nodes transition between the sleep, receive, and transmit states. We analyze Panda and select its parameters to maximize the ND rate subject to a homogeneous power budget. We also present Panda-D, designed for non-homogeneous EH nodes. We perform extensive testbed evaluations using the prototypes and study various design tradeoffs. We demonstrate a small difference (less then 2%) between experimental and analytical results, thereby confirming the modeling assumptions. Moreover, we show that Panda improves the ND rate by up to 3x compared to related protocols. Finally, we show that Panda-D operates well under non-homogeneous power harvesting.

Object tracking applications are gaining popularity and will soon utilize energy harvesting low-power wireless nodes where power is mostly consumed for neighbor discovery. Such applications require the design and experimentation with low-power neighbor discovery protocols. We demonstrate the Panda protocol [4, 5] implementation using commercial off-the-shelf energy harvesting devices, based on the TI eZ430-RF2500-SEH prototype. The prototypes harvest indoor light energy to perform power-aware neighbor discovery, while maintaining a power budget. A custom-designed online monitoring system interactively demonstrates the network dynamics, including the energy storage levels of the devices, the neighbor discovery events, and aggregate discovery statistics.

Object tracking applications are gaining popularity and will soon utilize energy harvesting (EH) low-power nodes that will consume power mostly for neighbor discovery (ND) (i.e., identifying nodes within communication range). Although ND protocols were developed for sensor networks, the challenges posed by emerging EH low-power transceivers were not addressed. Therefore, we design an ND protocol tailoredfor the characteristics of a representative EH prototype: the TI eZ430-RF2500-SEH. We present a generalized model of ND accounting for unique prototype characteristics (i.e., energy costs for transmission/reception, and transceiver state switching times/costs). Then, we present the Power Aware ND Asynchronously (Panda) protocol, in which nodes transition between the sleep, receive, and transmit states. We analyze Panda and select its parameters to maximize the ND rate subject to a homogeneous power budget. We also present Panda-D, designed for non-homogeneous EH nodes. We perform extensive testbed evaluations using the prototypes and study various design tradeoffs. We demonstrate a small difference (less than 2%) between experimental and analytical results, thereby confirming the modeling assumptions. Moreover, we show that Panda improves the ND rate by up to 3× compared with related protocols. Finally, we show that Panda-D operates well under non-homogeneous power harvesting.

We propose Joint-Family, a protocol that combines peer-to-peer (P2P) and adaptive bitrate (ABR) streaming for video-on-demand (VoD). While P2P for VoD and ABR have been proposed previously, they have not been studied together because they attempt to tackle problems with seemingly orthogonal goals. We motivate our approach through analysis that overcomes a misconception resulting from prior analytical work, and show that the popularity of a P2P swarm and seed staying time has a significant bearing on the achievable per-receiver download rate. Specifically, our analysis shows that popularity affects swarm efficiency when seeds stay “long enough”. We also show that ABR in a P2P setting helps viewers achieve higher playback rates and/or fewer interruptions. We develop the Joint-Family protocol based on the observations from our analysis. Peers in Joint-Family simultaneously participate in multiple swarms to exchange chunks of different bitrates. We adopt chunk, bitrate, and peer selection policies that minimize occurrence of interruptions while delivering high quality video and improving the efficiency of the system. Using traces from a large-scale commercial VoD service, we compare Joint-Family with existing approaches for P2P VoD and show that viewers in Joint-Family enjoy higher playback rates with minimal interruption, irrespective of video popularity.

Clouds commonly store Virtual Machine (VM) images on networked storage. This poses a serious potential scalability bottleneck as launching a single fresh VM instance requires, at minimum, several hundred MB of network reads. As this bottleneck occurs most severely during read-intensive launching of new VMs, we focus on scalably minimizing time to boot a VM and load its critical applications.

We explore distributed mechanisms for maintaining the physical layer connectivity of a mobile wireless network while still permitting significant area coverage. Moreover, we require that these mechanisms maintain connectivity despite the unpredictable wireless propagation behavior found in complex real-world environments. To this end, we propose the Spreadable Connected Autonomic Network (SCAN) algorithm, a fully distributed, on-line, low overhead mechanism for maintaining the connectivity of a mobile wireless network. SCAN leverages knowledge of the local (2-hop) network topology to enable each node to intelligently halt its own movement and thereby avoid network partitioning events. By relying on topology data instead of locality information and deterministic connectivity models, SCAN can be applied in a wide range of realistic operational environments. We believe it is for precisely this reason that, to our best knowledge, SCAN was the first such approach to be implemented in hardware. Here, we present results from our implementation of SCAN, finding that our mobile robotic testbed maintains full connectivity over 99% of the time. Moreover, SCAN achieves this in a complex indoor environment, while still allowing testbed nodes to cover a significant area.

We explore distributed mechanisms for maintaining the physical layer connectivity of a mobile wireless network while still permitting significant area coverage. Moreover, we require that these mechanisms maintain connectivity despite the unpredictable wireless propagation behavior found in complex real-world environments. To this end, we propose the Spreadable Connected Autonomic Network (SCAN) algorithm, a fully distributed, on-line, low overhead mechanism for maintaining the connectivity of a mobile wireless network. SCAN leverages knowledge of the local (2-hop) network topology to enable each node to intelligently halt its own movement and thereby avoid network partitioning events. By relying on topology data instead of locality information and deterministic connectivity models, SCAN can be applied in a wide range of realistic operational environments. We believe it is for precisely this reason that, to our best knowledge, SCAN was the first such approach to be implemented in hardware. Here, we present results from our implementation of SCAN, finding that our mobile robotic testbed maintains full connectivity over 99% of the time. Moreover, SCAN achieves this in a complex indoor environment, while still allowing testbed nodes to cover a significant area.

Internet service providers (ISPs) depend on one another to provide global network services. However, the profit-seeking nature of the ISPs leads to selfish behaviors that result in inefficiencies and disputes in the network. This concern is at the heart of the “network neutrality” debate, which also asks for an appropriate compensation structure that satisfies all types of ISPs. Our previous work showed in a general network model that the Shapley value has several desirable properties, and that if applied as the profit model, selfish ISPs would yield globally optimal routing and interconnecting decisions. In this paper, we use a more detailed and realistic network model with three classes of ISPs: content, transit, and eyeball. This additional detail enables us to delve much deeper into the implications of a Shapley settlement mechanism. We derive closed-form Shapley values for more structured ISP topologies and develop a dynamic programming procedure to compute the Shapley values under more diverse Internet topologies. We also identify the implications on the bilateral compensation between ISPs and the pricing structures for differentiated services. In practice, these results provide guidelines for solving disputes between ISPs and for establishing regulatory protocols for differentiated services and the industry.

With the convergence of ultra-low-power communications and energy-harvesting technologies, networking self-sustainable ubiquitous devices is becoming feasible. Hence, we have been recently developing new devices, referred to as Energy Harvesting Active Networked Tags (EnHANTs). These small, flexible, and energetically self-reliant tags can be seen as a new class of devices in the domain between RFIDs and sensor networks. EnHANTs are made possible by advances in ultra-lowpower ultra-wideband (UWB) communications and in organic semiconductor-based energy harvesting materials. They will enable novel tracking applications, such as continuous monitoring of objects and locating misplaced items. In this demo, we present phase I EnHANT prototypes. These prototypes are much larger than the envisioned EnHANTs and do not include custom-made UWB and organic electronic components. Yet, they serve as platforms for preliminary experiments and allow demonstrating energy harvesting-adaptive EnHANT communications. Each prototype is based on a MICA2 mote and includes a custom-designed sensor board with a light sensor and a solar cell, which are used to determine the light energy received from the environment. We have also designed a monitoring system which is used in the demo to show how the EnHANT prototypes adjust their communications patterns based on their energy harvesting parameters.

Virtual Appliances (VAs) are Virtual Machines (VMs) geared towards a specific set of tasks. They require little or no configuration, working out-of-the-box. VAs fit neatly into the Cloud Computing paradigm - many copies of an identical machine can be launched in a data center, or home/business users can grab the appliance they need from the cloud to run locally just for so long as required. Companies and projects whose sole offerings are VAs ready for either desktop or data center use [3, 11] attest to the growing popularity of VAs. VMware's Appliance directory alone currently lists over 1400 VAs available for the VMware family of Virtual Machine Monitors (VMMs) [13].

TCP has traditionally been considered inappropriate for real-time applications. Nonetheless, popular applications such as Skype use TCP since UDP packets cannot pass through restrictive network address translators (NATs) and firewalls. Motivated by this observation, we study the delay performance of TCP for real-time media flows. We develop an analytical performance model for the delay of TCP. We use extensive experiments to validate the model and to evaluate the impact of various TCP mechanisms on its delay performance. Based on our results, we derive the working region for VoIP and live video streaming applications and provide guidelines for delay-friendly TCP settings. Our research indicates that simple application-level schemes, such as packet splitting and parallel connections, can reduce the delay of real-time TCP flows by as much as 30% and 90%, respectively.

Within the current Internet, autonomous ISPs implement bilateral agreements, with each ISP establishing agreements that suit its own local objective to maximize its profit. Peering agreements based on local views and bilateral settlements, while expedient, encourage selfish routing strategies and discriminatory interconnections. From a more global perspective, such settlements reduce aggregate profits, limit the stability of routes, and discourage potentially useful peering/connectivity arrangements, thereby unnecessarily balkanizing the Internet. We show that if the distribution of profits is enforced at a global level, then there exist profit-sharing mechanisms derived from the coalition games concept ofShapley valueand its extensions that will encourage these selfish ISPs who seek to maximize their own profits to converge to a Nash equilibrium. We show that these profit-sharing schemes exhibit several fairness properties that support the argument that this distribution of profits is desirable. In addition, at the Nash equilibrium point, the routing and connecting/peering strategies maximize aggregate network profits and encourage ISP connectivity so as to limit balkanization.

We consider an end-to-end approach of inferring probabilistic data forwarding failures in an externally managed overlay network, where overlay nodes are independently operated by various administrative domains. Our optimization goal is to minimize the expected cost of correcting (i.e., diagnosing and repairing) all faulty overlay nodes that cannot properly deliver data. Instead of first checking the most likely faulty nodes as in conventional fault localization problems, we prove that an optimal strategy should start with checking one of the candidate nodes, which are identified based on a potential function that we develop. We propose several efficient heuristics for inferring the best node to be checked in large-scale networks. By extensive simulation, we show that we can infer the best node in at least 95 percent of time, and that first checking the candidate nodes rather than the most likely faulty nodes can decrease the checking cost of correcting all faulty nodes.

This paper presents the design challenges posed by a new class of ultra-low-power devices referred to as Energy-Harvesting Active Networked Tags (EnHANTs). EnHANTs are small, flexible, and self-reliant (in terms of energy devices that can be attached to objects that are traditionally not networked (e.g., books, clothing, and produce), thereby providing the infrastructure for various novel tracking applications. Examples of these applications include locating misplaced items, continuous monitoring of objects (items in a store, boxes in transit), and determining locations of disaster survivors. Recent advances in ultra-low-power wireless communications, ultra-wideband (UWB) circuit design, and organic electronic harvesting techniques will enable the realization of EnHANTs in the near future. In order for EnHANTs to rely on harvested energy, they have to spend significantly less energy than Bluetooth, Zigbee, and IEEE 802.15.4a devices. Moreover, the harvesting components and the ultra-low-power physical layer have special characteristics whose implications on the higher layers have yet to be studied (e.g., when using ultra-low-power circuits, the energy required to receive a bit is an order of magnitude higher than the energy required to transmit a bit). These special characteristics pose several new cross-layer research problems. In this paper, we describe the design challenges at the layers above the physical layer, point out relevant research directions, and outline possible starting points for solutions.

Currently deployed IEEE 802.11 WLANs (Wi-Fi networks) share access point (AP) bandwidth on a per-packet basis. However, the various stations communicating with the AP often have different signal qualities, resulting in different transmission rates. This induces a phenomenon known as the rate anomaly problem, in which stations with lower signal quality transmit at lower rates and consume a significant majority of airtime, thereby dramatically reducing the throughput of stations transmitting at high rates.We propose a practical, deployable system, called Soft-Repeater, in which stations cooperatively address the rate anomaly problem. Specifically, higher-rate Wi-Fi stations opportunistically transform themselves into repeaters for stations with low data-rates when transmitting to/from the AP. The key challenge is to determine when it is beneficial to enable the repeater functionality. In this paper, we propose an initiation protocol that ensures that repeater functionality is enabled only when appropriate. Also, our system can run directly on top of today's 802.11 infrastructure networks.We evaluate our system using simulation and testbed implementation, and find that SoftRepeater can improve cumulative throughput by up to 200%.

Internet service providers (ISPs) depend on one another to provide global network services. However, the profit-seeking nature of the ISPs leads to selfish behaviors that result in inefficiencies and disputes in the network. This concern is at the heart of the "network neutrality" debate, which also asks for an appropriate compensation structure that satisfies all types of ISPs. Our previous work showed in a general network model that the Shapley value has several desirable properties, and that if applied as the revenue model, selfish ISPs would yield globally optimal routing and interconnecting decisions.

TCP has traditionally been considered unfriendly for real-time applications. Nonetheless, popular applications such as Skype use TCP since UDP packets cannot pass through many NATs and firewalls. Motivated by this observation, we study the delay performance of TCP for real-time media flows. We develop an analytical performance model for the delay of TCP. We use extensive experiments to validate the model and to evaluate the impact of various TCP mechanisms on its delay performance. Based on our results, we derive the working region for VoIP and live video streaming applications and provide guidelines for delay-friendly TCP settings. Our research indicates that simple application-level schemes, such as packet splitting and parallel connections, can reduce the delay of real-time TCP flows by as much as 30% and 90%, respectively.

Within the current Internet, autonomous ISPs implement bilateral agreements, with each ISP establishing agreements that suit its own local objective to maximize its profit. Peering agreements based on local views and bilateral settlements, while expedient, encourage selfish routing strategies and discriminatory interconnections. From a more global perspective, such settlements reduce aggregate profits, limit the stability of routes, and discourage potentially useful peering/connectivity arrangements, thereby unnecessarily balkanizing the Internet. We show that if the distribution of profits is enforced at a global level, then there exist profit-sharing mechanisms derived from the coalition games concept of Shapley value and its extensions that will encourage these selfish ISPs who seek to maximize their own profits to converge to a Nash equilibrium. We show that these profit sharing schemes exhibit several fairness properties that support the argument that this distribution of profits is desirable. In addition, at the Nash equilibrium point, the routing and connecting/peering strategies maximize aggregate network profits, encourage ISP connectivity so as to limit balkanization.

We consider an end-to-end approach of inferring network faults that manifest in multiple protocol layers, with an optimization goal of minimizing the expected cost of correcting all faulty nodes. Instead of first checking the most likely faulty nodes as in conventional fault localization problems, we prove that an optimal strategy should start with checking one of the candidate nodes, which are identified based on a potential function that we develop. We propose several efficient heuristics for inferring the best node to be checked in large-scale networks. By extensive simulation, we show that we can infer the best node in at least 95%, and that checking first the candidate nodes rather than the most likely faulty nodes can decrease the checking cost of correcting all faulty nodes by up to 25%.

802.11a, b, and g standards were designed for deployment in cooperative environments, and hence do not include mechanisms to protect from jamming attacks. In this paper, we explore how to protect 802.11 networks from jamming attacks by having the legitimate transmission hop among channels to hide the transmission from the jammer. Using a combination of mathematical analysis and prototype experimentation in an 802.11a environment, we explore how much throughput can be maintained in comparison to the maintainable throughput in a cooperative, jam-free environment. Our experimental and analytical results show that in today's conventional 802.11a networks, we can achieve up to 60% of the original throughput. Our mathematical analysis allows us to extrapolate the throughput that can be maintained when the constraint on the number of orthogonal channels used for both legitimate communication and for jamming is relaxed.

We study the problem of aggregate querying over sensor networks where the network topology is continuously evolving. We develop scalable data aggregation techniques that remain efficient and accurate even as nodes move, join or leave the network. We present a novel distributed algorithm called CountTorrent, that enables fast estimation of certain classes of aggregate queries such as COUNT and SUM. CountTorrent does not require a static routing infrastructure, is easily implemented in a distributed setting, and can be used to inform all network nodes of the aggregate query result, instead of just the query initiator as is done in traditional query aggregation schemes. We evaluate its robustness and accuracy compared to previous aggregation approaches through simulations of dynamic and mobile sensor network environments and experiments on micaz motes. We show that in networks where the nodes are stationary, CountTorrent can provide 100% accurate aggregate results even in the presence of lossy links. In mobile sensor networks where the nodes constantly move and hence the network topology changes continuously, CountTorrent provides a close (within 10 -- 20%) estimate of the accurate aggregate query value to all nodes in the network at all times.

Blind scheduling policies schedule tasks without knowledge of the tasks' remaining processing times. Existing blind policies, such as FCFS, PS, and LAS, have proven useful in network and operating system applications, but each policy has a separate, vastly differing description, leading to separate and distinct implementations. This paper presents the design and implementation of a configurable blind scheduler that contains a continuous, tunable parameter. By merely changing the value of this parameter, the scheduler's policy exactly emulates or closely approximates several existing standard policies. Other settings enable policies whose behavior is a hybrid of these standards. We demonstrate the practical benefits of such a configurable scheduler by implementing it into the Linux operating system. We show that we can emulate the behavior of Linux's existing, more complex scheduler with a single (hybrid) setting of the parameter. We also show, using synthetic workloads, that the best value for the tunable parameter is not unique, but depends on distribution of the size of tasks arriving to the system. Finally, we use our formulation of the configurable scheduler to contrast the behavior of various blind schedulers by exploring how various properties of the scheduler change as we vary our scheduler's tunable parameter.

The distributed routing protocols in use today promise to operate correctly only if all nodes implement the protocol faithfully. A small insignificant set of nodes have, in the past, brought an entire network to a standstill by reporting incorrect route information. The damage caused by these erroneous reports, in some instances, could have been contained since incorrect route reports sometimes reveal themselves as inconsistencies in the state-information of correctly functioning nodes. By checking for such inconsitencies and taking preventive action, such as disregarding selected route-reports, a correctly functioning node could have limited the damage caused by the malfunctioning nodes.

To increase the utilization of the available frequency channel space in 802.11-based wireless mesh networks, recent work has explored solutions based on multi-radio stations. This paper reports on our design and experimental study of a distributed, self-stabilizing mechanism that assigns channels to multi-radio nodes in wireless mesh networks. We take a modular approach by decoupling the channel selection decision from the data forwarding mechanism, which makes our solution readily applicable to real-world operation when used with emerging multi-radio routing solutions. We demonstrate the efficacy of our protocol on a real-world, 14-node testbed comprised of nodes, each equipped with an 802.11a card and an 802.11g card. We show via extensive measurements on our testbed that our channel assignment algorithm improves the network capacity by 50% in comparison to a homogeneous channel assignment and by 20% in comparison to a random assignment.

Server providers that support e-commerce applications as a service for multiple e-commerce Web sites traditionally use a tiered server architecture. This architecture includes an application tier to process requests for dynamically generated content. How this tier is provisioned can significantly impact a provider's profit margin. In this article we study methods to provision servers in the application serving tier that increase a server provider's profits. First, we examine actual traces of request arrivals to the application tier of an e-commerce site, and show that the arrival process is effectively Poisson. Next, we construct an optimization problem in the context of a set of application servers modeled as M / G /1/ PS queueing systems, and derive three simple methods that approximate the allocation that maximizes profits. Simulation results demonstrate that our approximation methods achieve profits that are close to optimal, and are significantly higher than those achieved via simple heuristics.

In this paper, we examine the feasibility of sending real-time CBR workloads over TCP. This is motivated by the friendliness of NATs and firewalls towards TCP as opposed to UDP as well as by recent improvements in Internet's bandwidth and loss rates. Traditionally, TCP has been considered undesirable for real-time CBR workloads. We evaluate this assertion by developing a novel analytical tool that yields TCP's sender-to-receiver socket delay distribution for CBR workloads. A key insight gained is that the use of smaller than MSS-sized packets in CBR workloads can exploit the TCP's ACK counting mechanism thereby limiting the delay impact of congestion window variations. We leverage this insight to provide a heuristic and system-level guidelines for reducing TCP transport delays.

Aloha [1] and its slotted variant [2] are commonly deployed Medium Access Control (MAC) protocols in environments where multiple transmitting devices compete for a medium, yet may have difficulty sensing each other’s presence. This paper models and evaluates the throughput that can be achieved in a system where nodes compete for bandwidth using a generalized version of slotted- Aloha protocols. We evaluate the channel utilization and fairness of these types of protocols for a variety of node objectives, including maximizing aggregate throughput of the channel, each node greedily maximizing its own throughput, and attacker nodes that attempt to jam the channel. If all nodes are selfish and greedily attempt to maximize their own throughputs, a situation similar to the traditional Prisoner’s Dilemma[3] arises. Our results reveal that under heavy loads, greedy strategies reduce the utilization, and that attackers cannot do much better than attacking during randomly selected slots.

Abstract — While packet capture has been observed in real implementations of 802.11 devices, there is a lack of accurate models that describe the phenomenon. We present a general analytical model and an iterative method that predicts error probabilities and throughputs of packet transmissions with multiple senderreceiver pairs. Our model offers a more accurate prediction than previous work by taking into account the cumulative strength of interference signals and using the BER model to convert a signal to interference and noise ratio value to a bit error probability. This permits the analysis of packet reception at any transmission rate with interference from neighbors at any set of locations. We also prove that our iterative method converges, and we verify the accuracy of our model through simulations in Qualnet. Last, we present a rate assignment algorithm to reduce the average delay as an application of our analysis. I.

Sensor networks are especially useful in catastrophic or emergency scenarios such as floods, fires, terrorist attacks or earthquakes where human participation may be too dangerous. However, such disaster scenarios pose an interesting design challenge since the sensor nodes used to collect and communicate data may themselves fail suddenly and unpredictably, resulting in the loss of valuable data. Furthermore, because these networks are often expected to be deployed in response to a disaster, or because of sudden configuration changes due to failure, these networks are often expected to operate in a "zero-configuration" paradigm, where data collection and transmission must be initiated immediately, before the nodes have a chance to assess the current network topology. In this paper, we design and analyze techniques to increase "persistence" of sensed data, so that data is more likely to reach a data sink, even as network nodes fail. This is done by replicating data compactly at neighboring nodes using novel "Growth Codes" that increase in efficiency as data accumulates at the sink. We show that Growth Codes preserve more data in the presence of node failures than previously proposed erasure resilient techniques.

In a P2P system, a client peer may select one or more server peers to download a specific file. In a P2P resource economy, the server peers charge the client for the downloading. A server peer's price would naturally depend on the specific object being downloaded, the duration of the download, and the rate at which the download is to occur. The optimal peer selection problem is to select, from the set of peers that have the desired object, the subset of peers and download rates that minimizes cost. In this paper we examine a number of natural peer selection problems for both P2P downloading and P2P streaming. For downloading, we obtain the optimal solution for minimizing the download delay subject to a budget constraint, as well as the corresponding Nash equilibrium. For the streaming problem, we obtain a solution that minimizes cost subject to continuous playback while allowing for one or more server peers to fail during the streaming process. The methodologies developed in this paper are applicable to a variety of P2P resource economy problems.

To proactively defend against intruders from readily jeopardizing single-path data sessions, we propose a distributed secure multipath solution to route data across multiple paths so that intruders require much more resources to mount successful attacks. Our work exhibits several crucial properties that differentiate itself from previous approaches. They include (1) distributed routing decisions: routing decisions are made without the centralized information of the entire network topology, (2) bandwidth-constraint adaptation: the worst-case link attack is mitigated for any feasible session throughput subject to the link-bandwidth constraints, and (3) lexicographic protection: severe link attacks are suppressed based on lexicographic optimization. We devise two algorithms for the solution, termed the bound-control algorithm and the lex-control algorithm, and prove their convergence to the respective optimal solutions. Experiments show that the bound-control algorithm is more effective to prevent the worst-case single-link attack when compared to the single-path approach, and that the lex-control algorithm further enhances the bound-control algorithm by countering severe single-link attacks and various models of multi-link attacks. Moreover, the lex-control algorithm offers prominent protection after only a few execution rounds. Thus, system designers can sacrifice minimal routing security for significantly improved algorithm performance when deploying the distributed secure multipath solution.

A growing body of knowledge about misconfigurations and their effects on modern network routing protocols has been accumulated by network researchers and practitioners. The focus in identifying these anomalies and their effects has been on the particular and on short-term practicalities. To our knowledge, nobody has asked the broader and harder question: given a protocol P, what misconfigurations can be detected and how? Are there classes of misconfigurations that cannot be detected, and can these somehow be identified.We present preliminary results in our attempt to address this issue. We first classify detection methods into what we call weak detection and strong detection. A weak detection method is one that, given a node's state, checks specific properties that should hold when the protocol is being correctly implemented. It may however fail to identify a detectable misconfiguration because it did not verify the appropriate property. Strong detection methods must, in contrast, detect any misconfiguration that is detectable by any property.Our work investigates such strong detection techniques for different routing protocols. We present preliminary results and demonstrate an O(|V|3) algorithm that implements strong detection on the Distance Vector protocol.

The problem of designing efficient algorithms for sharing the cost of multicasting has recently received considerable attention. In this article, we examine the effect on the complexity of pricing when two flexibility-enhancing mechanisms are incorporated into the network model. In particular, we study a model where the session is offered at a number of different rates of transmission, and where there is a cost for enabling multicasting at each node of the network. We consider two techniques that have been used in practice to provide multiple rates: using a layered transmission scheme (called the layered paradigm ) and using different multicast groups for each possible rate (called the split session paradigm ). We demonstrate that the difference between these two paradigms has a significant impact on the complexity of pricing multicasting.For the layered paradigm, we provide a distributed algorithm for computing pricing efficiently in terms of local computation and message complexity. For the split session paradigm, on the other hand, we demonstrate that this problem can be solved in polynomial time if the number of possible rates is fixed, but if the number of rates is part of the input, then the problem becomes NP-Hard even to approximate. We also examine the effect of delivering the transmissions for the various rates from different locations within the network. We show that, in this case, the pricing problem becomes NP-Hard for the split session paradigm even for a fixed constant number of possible rates but if layering is used, then it can be solved in polynomial time by formulating the problem as a totally unimodular integer program.

Emerging large scale distributed networking systems, such as P2P file sharing systems, sensor networks, and ad hoc wireless networks, require replication of content, functionality, or configuration to enact or optimize communication tasks. The placement of these replicated resources can significantly impact performance. We present a novel self-stabilizing, fully distributed, asynchronous, scalable protocol that can be used to place replicated resources such that each node is "close" to some copy of any object. We describe our protocol in the context of a graph with colored nodes, where a node's color indicates the replica/task that it is assigned. Our combination of theoretical results and simulation prove stabilization of the protocol, and evaluate its performance in the context of convergence time, message transmissions, and color distance. Our results show that the protocol generates colorings that are close to the optimal under a set of metrics, making such a protocol ideal for emerging networking systems.

Today's Internet periodically suffers from hot spots, a.k.a., flash crowds. A hot spot is typically triggered by an unanticipated news event that triggers an unanticipated surge of users that request data objects from a particular site, temporarily overwhelming the site's delivery capabilities. During this time, the large majority of users that attempt to get these objects face the frustrating experience of not being able to retrieve the content they want while still being able to communicate effectively with all other parts of the network. In this paper, we examine whether simple, undirected peer-to-peer search protocols can be used as a backup to deliver content whose popularity suddenly spikes. We model a simple, representative, undirected peer-to-peer search protocol in which clients cache only those objects they have explicitly requested. Because the object that becomes hot initially has limited popularity, the number of cache points, were they to remain fixed, would be insufficient to handle the level of demand during the flash crowd. However, as searches complete, more copies of the object become available. We analyze this natural scaling phenomenon and show that during the flash crowd, copies are distributed to requesting clients at a fast enough rate such that these simple protocols can indeed be used to scalably retrieve content that suddenly becomes "hot".

Demand for content served by a provider can fluctuate with time, complicating the task of provisioning serving resources so that requests for its content are not rejected. One way to address this problem is to have providers form a collective in which they pool together their serving resources to assist in servicing requests for one another's content. In this paper, we determine the conditions under which a provider's participation in a collective reduces the rejection rate of requests for its content - a property that is necessary for such a provider to justify its participation within the collective. We show that all request rejection rates are reduced when the collective is formed from a homogeneous set of providers, but that some rates can increase within heterogeneous sets. We also show that, asymptotically, growing the size of the collective will sometimes, but not always, resolve this problem. We explore the use of thresholding techniques, where each collective participant sets aside a portion of its serving resources to serve only requests for its own content. We show that thresholding allows a more diverse set of providers to benefit from the collective model, making collectives a more viable option for content delivery services.

The volume of multimedia data, including video, served through peer-to-peer (P2P) networks is growing rapidly. Unfortunately, high bandwidth transfer rates are rarely available to P2P clients on a consistent basis, making it difficult to use P2P networks to stream video for on-line viewing. In this paper, we develop and evaluate on-line algorithms that coordinate the pre-fetching of scalably-coded variable bitrate video. These algorithms are ideal for P2P environments in that they require no knowledge of the future variability or availability of bandwidth, yet produce a playback whose average rate and variability are comparable to the best off-line prefetching algorithms that have total future knowledge. To show this, we develop an off-line algorithm that provably optimizes quality and variability metrics. Using simulations based on actual P2P traces, we compare our on-line algorithms to the optimal off-line algorithm and find that our novel on-line algorithms exhibit near-optimal performance and significantly outperform more traditional pre-fetching methods.

Soft state has been a mantra of Internet protocol design for the past decade. System designers build protocols that implement soft state mechanisms based on intuition or on qualitative arguments that the design is "better", yet there has never been a formal performance evaluation study that draws the same conclusion. In fact, previous attempts [P. Ji et al., 2003 and S. Raman et al., 1999] to build such a quantitative argument have found that pure soft state protocols significantly under-perform their hard state counterparts, and that only soft-hard hybrids can match hard state protocol performance. In this paper, we argue otherwise. We develop models that provide a performance-oriented explanation and justification of the Internet designer's intuition. The novel observation is that, if network conditions are known, a hard state protocol can always be configured to outperform its soft state counterpart. However, in reality, network conditions are unpredictable, and that soft state protocols are much more resilient to unanticipated fluctuations in these conditions.

Server providers that support e-commerce applications as a service to multiple e-commerce websites traditionally use a tiered server architecture. This architecture includes an application tier to process requests that require dynamically generated content. How this tier is provisioned can significantly impact a provider's profit margin. We study methods to provision servers in the application serving tier to increase a server provider's profits. First, we examine actual traces of request arrivals to the application tier of e-commerce sites, and show that the arrival process is effectively Poisson. Next, we construct an optimization problem in the context of a set of application servers modeled as M/G/l/PS queueing systems, and derive three simple methods to approximate the allocation that maximizes profits. Simulation results demonstrate that our approximation methods achieve profits that are close to optimal and are significantly higher than those achieved via simple heuristics.

Quality of service for high-bandwidth or delay-sensitive applications in the Internet, such as streaming media and online games, can be significantly improved by replicating server content. We present a decentralized algorithm that allocates server resources to replicated servers in large-scale client-server networks to reduce network distance between each client and the nearby replicated server hosting the resources of interest to that client. Preliminary simulation results show that our algorithm converges quickly to an allocation that reduces the expected client-server distance by almost half compared to the distance when the assignment of replicated servers is done at random.

No abstract available.

We propose an architecture called secure overlay services (SOS) that proactively prevents denial of service (DoS) attacks, including distributed (DDoS) attacks; it is geared toward supporting emergency services, or similar types of communication. The architecture uses a combination of secure overlay tunneling, routing via consistent hashing, and filtering. We reduce the probability of successful attacks by: 1) performing intensive filtering near protected network edges, pushing the attack point perimeter into the core of the network, where high-speed routers can handle the volume of attack traffic and 2) introducing randomness and anonymity into the forwarding architecture, making it difficult for an attacker to target nodes along the path to a specific SOS-protected destination. Using simple analytical models, we evaluate the likelihood that an attacker can successfully launch a DoS attack against an SOS-protected network. Our analysis demonstrates that such an architecture reduces the likelihood of a successful attack to minuscule levels. Our performance measurements using a prototype implementation indicate an increase in end-to-end latency by a factor of two for the general case, and an average heal time of less than 10 s.

An Internet flash crowd (also known as hot spots) is a phenomenon that results from a sudden, unpredicted increase in an on-line object's popularity. Currently, there is no efficient means within the Internet to deliver Web objects scalably under hot spot conditions to all clients that desire the object. We present peer-to-peer (P2P) randomized overlays to obviate flash-crowd symptoms (PROOFS), a simple, lightweight, P2P approach that uses randomized overlay construction and randomized, scoped searches to locate and deliver objects efficiently under heavy demand to all users that desire them. We evaluate PROOFS' robustness in environments in which clients join and leave the P2P network, as well as in environments in which clients are not always fully cooperative. Through a mix of simulation and prototype experimentation in the Internet, we show that randomized approaches like PROOFS should effectively relieve flash crowd symptoms in dynamic, limited-participation environments.

We present WebSOS, a novel overlay-based architecture that provides guaranteed access to a web server that is targeted by a denial of service (DoS) attack. Our approach exploits two key characteristics of the web environment: its design around a human-centric interface, and the extensibility inherent in many browsers through downloadable "applets." We guarantee access to a web server for a large number of previously unknown users, without requiring pre-existing trust relationships between users and the system.Our prototype requires no modifications to either servers or browsers, and makes use of graphical Turing tests, web proxies, and client authentication using the SSL/TLS protocol, all readily supported by modern browsers. We use the WebSOS prototype to conduct a performance evaluation over the Internet using PlanetLab, a testbed for experimentation with network overlays. We determine the end-to-end latency using both a Chord-based approach and our shortcut extension. Our evaluation shows the latency increase by a factor of 7 and 2 respectively, confirming our simulation results.

Emerging large scale distributed networking systems, such as P2P file sharing systems, sensor networks, and ad hoc wireless networks, require replication of content, functionality, or configuration to enact or optimize communication tasks. The placement of these replicated resources can significantly impact performance. We present a novel self-stabilizing, fully distributed, asynchronous, scalable protocol that can be used to place replicated resources such that each node is "close" to some copy of any object. We describe our protocol in the context of a graph with colored nodes, where a node's color indicates the replica/task that it is assigned. Our combination of theoretical results and simulation prove stabilization of the protocol, and evaluate its performance in the context of convergence time, message transmissions, and color distance. Our results show that the protocol generates colorings that are close to the optimal under a set of metrics, making such a protocol ideal for emerging networking systems.

Internet flash crowds (a.k.a. hot spots) are a phenomenon that result from a sudden, unpredicted increase in an on-line object's popularity. Currently, there is no efficient means within the Internet to scalably deliver Web objects under hot spot conditions to all clients that desire the object. We present PROOFS: a simple, lightweight, peer-to-peer (P2P) approach that uses randomized overlay construction and randomized, scoped searches to efficiently locate and deliver objects under heavy demand to all users that desire them. We evaluate PROOFS' robustness in environments in which clients join and leave the P2P network as well as in environments in which clients are not always fully cooperative. Through a mix of simulation and prototype experimentation in the Internet, we show that randomized approaches like PROOFS should effectively relieve flash crowd symptoms in dynamic, limited-participation environments.

Denial of service (DoS) attacks continue to threaten the reliability of networking systems. Previous approaches for protecting networks from DoS attacks are reactive in that they wait for an attack to be launched before taking appropriate measures to protect the network. This leaves the door open for other attacks that use more sophisticated methods to mask their traffic.We propose an architecture called Secure Overlay Services (SOS) that proactively prevents DoS attacks, geared toward supporting Emergency Services or similar types of communication. The architecture is constructed using a combination of secure overlay tunneling, routing via consistent hashing, and filtering. We reduce the probability of successful attacks by (i) performing intensive filtering near protected network edges, pushing the attack point perimeter into the core of the network, where high-speed routers can handle the volume of attack traffic, and (ii) introducing randomness and anonymity into the architecture, making it difficult for an attacker to target nodes along the path to a specific SOS-protected destination.Using simple analytical models, we evaluate the likelihood that an attacker can successfully launch a DoS attack against an SOS-protected network. Our analysis demonstrates that such an architecture reduces the likelihood of a successful attack to minuscule levels.

Many definitions of fairness for multicast networks assume that sessions are single rate, requiring that each multicast session transmits data to all of its receivers at the same rate. These definitions do not account for multirate approaches, such as layering, that permit receiving rates within a session to be chosen independently. We identify four desirable fairness properties for multicast networks, derived from properties that hold within the max-min fair allocations of unicast networks. We extend the definition of multicast max-min fairness to networks that contain multirate sessions, and show that all four fairness properties hold in a multirate max-min fair allocation, but need not hold in a single-rate max-min fair allocation. We then show that multirate max-min fair rate allocations can be achieved via intra-session coordinated joins and leaves of multicast groups. However, in the absence of coordination, the resulting max-min fair rate allocation uses link bandwidth inefficiently, and does not exhibit some of the desirable fairness properties. We evaluate this inefficiency for several layered multirate congestion control schemes, and find that, in a protocol where the sender coordinates joins, this inefficiency has minimal impact on desirable fairness properties. Our results indicate that sender-coordinated layered protocols show promise for achieving desirable fairness properties for allocations in large-scale multicast networks.

Current Internet congestion control protocols operate independently on a per-flow basis. Recent work has demonstrated that cooperative congestion control strategies between flows can improve performance for a variety of applications, ranging from aggregated TCP transmissions to multiple-sender multicast applications. However, in order for this cooperation to be effective, one must first identify the flows that are congested at the same set of resources. We present techniques based on loss or delay observations at end hosts to infer whether or not two flows experiencing congestion are congested at the same network resources. Our novel result is that such detection can be achieved for unicast flows, but the techniques can also be applied to multicast flows. We validate these techniques via queueing analysis, simulation and experimentation within the Internet. In addition, we demonstrate preliminary simulation results that show that the delay-based technique can determine whether two TCP flows are congested at the same set of resources. We also propose metrics that can be used as a measure of the amount of congestion sharing between two flows.

Current Internet congestion control protocols operate independently on a per-flow basis. Recent work has demonstrated that cooperative congestion control strategies between flows can improve performance for a variety of applications, ranging from aggregated TCP transmissions to multiple-sender multicast applications. However, in order for this cooperation to be effective, one must first identify the flows that are congested at the same set of resources. In this paper, we present techniques based on loss or delay observations at end-hosts to infer whether or not two flows experiencing congestion are congested at the same network resources. We validate these techniques via queueing analysis, simulation, and experimentation within the Internet.

We propose and evaluate novel reliable multicast protocols that combine active repair service (a.k.a. local recovery) and parity encoding (a.k.a. forward error correction or FEC) techniques. We show that, compared to other repair service protocols, our protocols require less buffer inside the network, maintain the low bandwidth requirements of previously proposed repair service/FEC combination protocols, and reduce the amount of FEC processing at repair servers, moving more of this processing to the end-hosts. We also examine repair service/FEC combination protocols in an environment where loss rates differ across domains within the network. We find that repair services are more effective than FEC at reducing bandwidth utilization in such environments. Furthermore, adding FEC to a repair services protocol not only reduces buffer requirements at repair servers, but also reduces bandwidth utilization in domains with high loss, or in domains with large populations of receivers.

169-182