In causal inference with observational studies, synthetic control (SC) has emerged as a prominent tool. SC has traditionally been applied to aggregate-level datasets, but more recent work has extended its use to individual-level data. As they contain a greater number of observed units, this shift introduces the curse of dimensionality to SC. To address this, we propose Cluster Synthetic Control (ClusterSC), based on the idea that groups of individuals may exist where behavior aligns internally but diverges between groups. ClusterSC incorporates a clustering step to select only the relevant donors for the target. We provide theoretical guarantees on the improvements induced by ClusterSC, supported by empirical demonstrations on synthetic and real-world datasets. The results indicate that ClusterSC consistently outperforms classical SC approaches.

Synthetic control is a causal inference tool used to estimate the treatment effects of an intervention by creating synthetic counterfactual data. This approach combines measurements from other similar observations (i.e., donor pool) to predict a counterfactual time series of interest (i.e., target unit) by analyzing the relationship between the target and the donor pool before the intervention. As synthetic control tools are increasingly applied to sensitive or proprietary data, formal privacy protections are often required. In this work, we suggest the first algorithms for differentially private synthetic control with explicit error bounds based on the analysis of the sensitivity of the synthetic control query. Our approach builds upon tools from non-private synthetic control and differentially private empirical risk minimization. We empirically evaluate the performance of our algorithms and show favorable results in a variety of parameter regimes.

Synthetic control (SC) methods have been widely applied to estimate the causal effect of large-scale interventions, e.g., the state-wide effect of a change in policy. The idea of synthetic controls is to approximate one unit’s counterfactual outcomes using a weighted combination of some other units’ observed outcomes. The motivating question of this paper is: how does the SC strategy lead to valid causal inferences? We address this question by re-formulating the causal inference problem targeted by SC with a more fine-grained model, where we change the unit of analysis from “large units" (e.g., states) to “small units" (e.g., individuals in states). Under the re-formulation, we derive sufficient conditions for the non-parametric causal identification of the causal effect. We show that, in some settings, existing linear SC estimators are valid even when the data generating process is non-linear. We highlight two implications of the reformulation: 1) it clarifies where “linearity" comes from, and how it falls naturally out of the more fine-grained and flexible model; 2) it suggests new ways of using available data with SC methods for valid causal inference, in particular, new ways of selecting observations from which to estimate the counterfactual.

BBR, a congestion control algorithm proposed by Google, regulates the source sending rate by deriving an estimate of the bottleneck’s available bandwidth and RTT of the path. The initial version of BBR, called BBRvl, was found to be unfair, getting higher than the fair share of bandwidth when co-existing on bottleneck links with other congestion control algorithms. It also does not perform as well with networks having routers with shallow buffers. To overcome these concerns, a newer version, called BBRv2, has been proposed. Our goal in this paper is to understand the differences between the two versions and examine the primary reasons behind the improvement in performance of BBRv2. We present an experimental evaluation of BBRvl and BBRv2, evaluating their fairness across connections using the same protocol (intra-protocol fairness) and using different protocols (inter-protocol fairness) as well as delay and link utilization. From experiments with shallow and deep buffers, BBRv2 is most effective when it uses Explicit Congestion Notification (ECN), but fairness issues continue to exist in BBRv2 when ECN is disabled. A concern for BBRv2 is that it is somewhat complex to deploy in Wide Area Networks (WAN) because of the dependency with the DCTCP-style reduction of the congestion window, which is primarily usable in low-feedback delay Data Center Networks.

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.

Data center networks, and especially drop-free RoCEv2 networks require efficient congestion control protocols. DCQCN (ECN-based) and TIMELY (delay-based) are two recent proposals for this purpose. In this paper, we analyze DCQCN and TIMELY using fluid models and simulations, for stability, convergence, fairness and flow completion time. We uncover several surprising behaviors of these protocols. For example, we show that DCQCN exhibits non-monotonic stability behavior, and that TIMELY can converge to stable regime with arbitrary unfairness. We propose simple fixes and tuning for ensuring that both protocols converge to and are stable at the fair share point. Finally, using lessons learnt from the analysis, we address the broader question: are there fundamental reasons to prefer either ECN or delay for end-to-end congestion control in data center networks? We argue that ECN is a better congestion signal, due to the way modern switches mark packets, and due to a fundamental limitation of end-to-end delay-based protocols, that we derive.

Advertising is a significant source of revenue for most online social networks. Conventional online advertising methods need to be customized for online social networks in order to address their distinct characteristics. Recent experimental studies have shown that providing social cues along with ads, e.g. information about friends liking the ad or clicking on an ad, leads to higher click rates. In other words, the probability of a user clicking an ad is a function of the set of friends that have clicked the ad. In this work, we propose formal probabilistic models to capture this phenomenon, and study the algorithmic problem that then arises. Our work is in the context of display advertising where a contract is signed to show an ad to a pre-determined number of users. The problem we study is the following: given a certain number of impressions, what is the optimal display strategy, i.e. the optimal order and the subset of users to show the ad to, so as to maximize the expected number of clicks? Unlike previous models of influence maximization, we show that this optimization problem is hard to approximate in general, and that it is related to finding dense subgraphs of a given size. In light of the hardness result, we propose several heuristic algorithms including a two-stage algorithm inspired by influence-and-exploit strategies in viral marketing. We evaluate the performance of these heuristics on real data sets, and observe that our two-stage heuristic significantly outperforms the natural baselines.

The evolution of the Internet has manifested itself in many ways: the traffic characteristics, the interconnection topologies, and the business relationships among the autonomous components. It is important to understand why (and how) this evolution came about, and how the interplay of these dynamics may affect future evolution and services. We propose a network-aware, macroscopic model that captures the characteristics and interactions of the application and network providers, and show how it leads to a market equilibrium of the ecosystem. By analyzing the driving forces and the dynamics of the market equilibrium, we obtain some fundamental understandings of the cause and effect of the Internet evolution, which explain why some historical and recent evolutions have happened. Furthermore, by projecting the likely future evolutions, our model can help application and network providers to make informed business decisions so as to succeed in this competitive ecosystem.

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.

Peer-to-Peer (P2P) systems have evolved from being used for file sharing to delivering streaming video on demand (VoD). The policies adopted in P2P VoD, however, have not taken user viewing behavior - that users abandon videos - into account. We show that abandonment can result in increased interruptions and wasted resources. As a result, we reconsider the set of policies to use in the presence of abandonment. Our goal is to balance the conflicting needs of delivering videos without interruptions while minimizing wastage. We find that an Earliest-First chunk selection policy in conjunction with the Earliest-Deadline peer selection policy allows us to achieve high download rates. We take advantage of abandonment by converting peers to “partial seeds”; this increases capacity. We minimize wastage by using a playback lookahead window. We use analysis and simulation experiments using real-world traces to show the effectiveness of our approach.

The evolution of the Internet has manifested itself in many ways: the traffic characteristics, the interconnection topologies and the business relationships among the autonomous components. It is important to understand why (and how) this evolution came about, and how the interplay of these dynamics may affect future evolution and services. We propose a network aware, macroscopic model that captures the characteristics and interactions of the application and network providers, and show how it leads to a market equilibrium of the ecosystem. By analyzing the driving forces and the dynamics of the market equilibrium, we obtain some fundamental understandings of the cause and effect of the Internet evolution, which explain why some historical and recent evolutions have happened. Furthermore, by projecting the likely future evolutions, our model can help application and network providers to make informed business decisions so as to succeed in this competitive ecosystem.

Network neutrality and the role of regulation on the Internet have been heavily debated in recent times. Among the various definitions of network neutrality, we focus on the one that prohibits paid prioritization of content. We develop a model of the Internet ecosystem in terms of three primary players: consumers, ISPs, and content providers. We analyze this issue from the point of view of the consumer and target the desired system state that maximizes consumer utility. By analyzing various structures of an ISP market, we obtain different conclusions on the desirability of regulation. We also introduce the notion of a Public Option ISP, an ISP that carries traffic in a network-neutral manner. We find: in a monopolistic scenario, network-neutral regulations might benefit consumers, however the introduction of a Public Option ISP is even better as it aligns the interests of the monopolistic ISP with the consumer utility; and in an oligopolistic scenario, the presence of a Public Option ISP is again preferable to network-neutral regulations, although the presence of competing nonneutral ISPs provides the most desirable situation for the consumers.

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.

In this paper, we develop the notion of congestion equilibrium in large scale networks, with the specific goal of understanding the modern multiparty Internet ecosystem comprising of content providers, ISPs and users. We show that the concept of "congestion-taking" is analogous to the concept of "price-taking" in classical market economics. With a wide variety of congestion metrics and under very mild assumptions on the congestion dynamics, we characterize various properties of congestion equilibria and develop algorithms to compute them for large scale networks. Our work provides a new way to model and analyze modern large scale network-economic systems that have a complex interaction of engineering and economics.

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.

Network neutrality and the role of regulation on the Internet have been heavily debated in recent times. Amongst the various definitions of network neutrality, we focus on the one which prohibits paid prioritization of content. We develop a model of the Internet ecosystem in terms of three primary players: consumers, ISPs and content providers. We analyze this issue from the point of view of the consumer, and target the desired system state that maximizes consumer surplus.

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.

International audience

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].

No abstract available.

A new generation of content delivery networks for live streaming, video on demand, and software updates takes advantage of a peer-to-peer architecture to reduce their operating cost. In contrast with previous uncoordinated peer-to-peer schemes, users opt-in to dedicate part of the resources they own to help the content delivery, in exchange for receiving the same service at a reduced price. Such incentive mechanisms are appealing, as they simplify coordination and accounting. However, they also increase a user's expectation that she will receive a fair price for the resources she provides. Addressing this issue carefully is critical in ensuring that all interested parties--including the provider--are willing to participate in such a system, thereby guaranteeing its stability.

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.

Peer-to-peer (P2P) systems in general, and BitTorrent (BT) specifically, have been of significant interest to researchers and Internet users alike. Existing models of BT abstract away certain characteristics of the protocol that are important, which we address in this work. We present a simple yet accurate and easily extensible model of BT. The model's accuracy is validated through a rigorous simulation-based study and its extensibility is illustrated by incorporating recently proposed approaches to protocol changes in BT.

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.

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%.

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.

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.

It is a commonly held belief that IPv6 provides greater security against random-scanning worms by virtue of a very sparse address space. We show that an intelligent worm can exploit the directory and naming services necessary for the functioning of any network, and we model the behavior of such a worm in this paper. We explore via analysis and simulation the spread of such worms in an IPv6 Internet. Our results indicate that such a worm can exhibit propagation speeds comparable to an IPv4 random-scanning worm. We develop a detailed analytical model that reveals the relationship between network parameters and the spreading rate of the worm in an IPv6 world. We also develop a simulator based on our analytical model. Simulation results based on parameters chosen from real measurements and the current Internet indicate that an intelligent worm can spread surprising fast in an IPv6 world by using simple strategies. The performance of the worm depends heavily on these strategies, which in turn depend on how secure the directory and naming services of a network are. As a result, additional work is needed in developing detection and defense mechanisms against future worms, and our work identifies directory and naming services as the natural place to do it.

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.

In this paper we introduce an innovation in differentiated services architecture consisting of adaptive two-level coloring at the edge and preferential marking at the core. We identify general properties of these two processes which, when met, guarantee a desirable fixed point for the network; i.e., one where aggregated flow rates meet or exceed given targets in an over-provisioned network. Specific mechanisms realizing the aforementioned properties lead to so-called active rate management controllers for edge coloring, and a preferentially-marking, active queue management controller at the core. We discuss stability of the fixed point for this network, and validate results using ns simulations.

We pose the question of how to encourage the resource sharing in a distributed, multi-provider environment, where each node, or provider, has local work but is able to accept additional work from other nodes/providers if there is available capacity. An instance of such an environment is found in content delivery, where. numerous, competing providers can work together if enough benefit is to be gained from doing so. We model individual provider behavior as essentially selfish, and then propose pricing schemes to exploit the selfishness to achieve system wide performance gains. We employ a game theoretic framework to analyze the problem, and come up with a time-dependent, noncooperative network equilibrium model. To influence the system towards the positive end of resource sharing, we suggest the creation of a monetary unit, tokens, whose exchange encourages a more efficient use of system-wide capacity, and whose effect is regulated by the pricing scheme in place. The impact of the different node behavior, model parameters, and pricing schemes in influencing the system performance is investigated through simulation. This framework can be combined with distance and round trip time to calibrate redirection behavior of distributed server environments.

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.

In this work we develop stability conditions for congestion control of the present Internet characterized by TCP-controlled sources and buffer-based active queue management (AQM) schemes. Prevailing stability results are geared towards rate-based AQMs and are not applicable to the class of networks considered here. Our new conditions can be expressed entirely in terms of network parameters, i.e., routing, which make them useful in the design of buffer-based AQMs such as RED, REM and PI.

Managing the performance of multiple-tiered Web sites under high client loads is a critical problem with the advent of dynamic content and database-driven servers on the Internet. This paper presents a control-theoretic approach for admission control in multitiered Web sites that both prevents overload and enforces absolute client response times, while still maintaining high throughput under load. We use classical control theoretic techniques to design a proportional integral (PI) controller for admission control of client HTTP requests. In addition, we present a processor-sharing model that is used to make the controller self-tuning, so that no parameter setting is required beyond a target response time. Our controller is implemented as a proxy, called Yaksha, which operates by taking simple external measurements of the client response times. Our design is noninvasive and requires minimal operator intervention. We evaluate our techniques experimentally using a 3-tiered dynamic content Web site as a testbed. Using the industry standard TPC-W client workload generator, we study the performance of the PI admission controller with extensive experiments. We show that the controller effectively bounds the response times of requests for dynamic content while still maintaining high throughput levels, even when the client request rate is many times that of the server's maximum processing rate. We demonstrate the effectiveness of our self-tuning mechanism, showing that it responds and adapts smoothly to changes in the workload.

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.

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.

Congestion control in TCP/AQM networks is expected to perform well for a wide-range of conditions, but recent advances in modeling and analysis indicate that present AQM (active queue management) schemes need an extra dose of adaptability to cope. The paper answers the call and proposes a self-tuning structure wherein AQM parameters are automatically tuned in response to on-line estimation of link capacity and traffic load. This approach is applicable to any AQM scheme that is parameterizable in terms of link capacity and TCP load. We describe this self-tuning structure, illustrate its application to PI (proportional-integral) and RED (random early detection) AQMs, provide stability analysis, and conduct ns simulations to compare with both fixed AQM schemes and the recently proposed adaptive RED.

Routers handle data packets from sources unresponsive to TCP's congestion avoidance feedback. We are interested in the impact these sources have on active queue management (AQM) control of long-lived TCP traffic. In this paper, we combine models of TCP/AQM dynamics with models of unresponsive traffic to analyze the effects on AQM performance.

In this paper we present a scalable model of a network of Active Queue Management (AQM) routers serving a large population of TCP flows. We present efficient solution techniques that allow one to obtain the transient behavior of the average queue lengths, packet loss probabilities, and average end-to-end latencies. We model different versions of TCP as well as different versions of RED, the most popular AQM scheme currently in use. Comparisons between our models andns simulation show our models to be quite accurate while at the same time requiring substantially less time to solve, especially when workloads and bandwidths are high. Categories and Subject Descriptors

Congestion control in TCP/AQM networks is expected to perform well for a wide-range of conditions, but recent advances in modeling and analysis indicate that present AQM schemes need an extra dose of adaptability to cope. This paper answers the call and proposes a self-tuning structure wherein AQM parameters are automatically tuned in response to on-line estimation of link capacity and traffic load. This approach is applicable to any AQM scheme that is parameterizable in terms of link capacity and TCP load. In this paper, we will describe this self-tuning structure, illustrate its application to PI and RED AQMs, provide stability analysis, and conduct ns simulations to compare with both fixed AQM schemes and the recently proposed adaptive RED.

In this paper we propose a new paradigm for a Differentiated Service (DiffServ) network consisting of two-color marking at the edges of the network using token buckets coupled with differential treatment in the core. Using fluid-flow modelling, we present existence conditions for token-bucket rates and differential marking probabilities at the core that result in all edges receiving at least their minimum guaranteed rates. We then present an integrated DiffServ architecture comprising of an active rate management controller at the marking edge and a two-level active queue management controller at the core. The validity of the fluid flow model and performance of this new scheme are verified using ns simulations.

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.

We use a previously developed nonlinear dynamic model of TCP to analyze and design active queue management (AQM) control systems using random early detection (RED). First, we linearize the interconnection of TCP and a bottlenecked queue and discuss its feedback properties in terms of network parameters such as link capacity, load and round-trip time. Using this model, we next design an AQM control system using the RED scheme by relating its free parameters such as the low-pass filter break point and loss probability profile to the network parameters. We present guidelines for designing linearly stable systems subject to network parameters like propagation delay and load level. Robustness to variations in system loads is a prime objective. We present no simulations to support our analysis.

In this paper we study a previously developed linearized model of TCP and active queue management (AQM). We use classical control system techniques to develop controllers well suited for the application. The controllers are shown to have better theoretical properties than the well known RED controller. We present guidelines for designing stable controllers subject to network parameters like load level propagation delay etc. We also present simple implementation techniques which require a minimal change to RED implementations. The performance of the controllers are verified and compared with RED using ns simulations. The second of our designs, the proportional integral (PI) controller is shown to outperform RED significantly.

151-160

We present a memory efficient method for transposing a run-length encoded bi-level image. Image transposing is a commonly used operation for affine transformations such as document image deskewing. The best existing method for transposing a run-length image is the pxy table based method. For images of typical engineering drawings, which are large, crowded and noisy, this method requires an exorbitant amount of memory. The method proposed uses a very compact representation of run-length encoded images. Also, it bypasses certain steps from the pxy table based method. Consequently, the saving in memory use is proportional to the number of horizontal runs and the number of vertical (transposed) runs. The computation time for both the methods is almost identical.

We have developed an efficient method to extract straight lines at any orientation from a line drawing. The method works by extracting the horizontal and vertical lines using the FAST method, detecting the angles of the other lines and applying the FAST method again while the image is rotated to each corresponding angle. The method is efficient because it is based on very efficient line finding, transposition, and rotation operations which work over the run-length representation of the line drawing.

This paper describes a methodology to interpret the information from telephone company DSX assignment table drawings. Horizontal lines are found using an efficient algorithm that works over the run-length encoded representation of the image. For vertical lines, the image is transposed using an efficient method we developed, and the algorithm for horizontal lines is applied again. Using the information about the lines, the tabular structures are extracted by finding biconnected components on the graph formed by the lines and their intersections. A methodology has also been developed for the representation of end access to the entries inside the tables.

We present efficient techniques for the interpretation and representation of tabular documents. Our goal is to achieve processing times that are fast enough for an interactive table conversion system. The techniques are based on the run-length encoded representation of scanned documents. We use DSX assignment tables, a predominant type of engineering drawing in telephone company central offices, as sample images in this paper. However, the techniques presented can be applied directly to tabular documents in any application.