Data plane verification (DPV) analyzes routing tables and detects routing abnormalities and policy violations during network operation and planning. Thus, it has become an important tool to harden the networking infrastructure and the computing systems built on top. Substantial advancements have been made in the last decade and state-of-the-art DPV systems can achieve sub-$\mu$s verification for an update of a single forwarding rule. In this article, we introducefast inverse model transformation(FIMT), the first theoretical framework to systematically model and analyze centralized DPV systems. FIMT reveals the algebraic structure in themodel updateprocess, a key step in fast DPV systems. Thus, it can systematically analyze the correctness of several DPV systems and optimization techniques, using algebraic properties. The theory also guides the design and implementation of Uimt, a generic DPV framework with provable optimization techniques. Using Uimt, we create two variants of existing DPV systems, NeoFlash and NeoDeltaNet. Evaluations show that NeoFlash outperforms existing state-of-the-art centralized DPV systems in various datasets and reveal insights to key techniques towards fast DPV.

Atomic predicate is a key enabler to the rapid development of data plane verification, a technique to monitor and verify correctness of forwarding rules. Binary Decision Diagram (BDD) is widely used as the representation of atomic predicates for its simplicity of use, memory efficiency, and good performance when verifying general forwarding behaviors. However, building the atomic predicates is still the bottleneck in real-time data plane verification for large-scale networks, as existing BDD libraries do not scale well. In this paper, we identify the root cause of the inefficiency: general-purpose BDD libraries are aimed at speeding up a single BDD operation using parallelism rather than a batch of operations. Further, we propose TOBDD, a throughput-optimized BDD library that enables scaling of real-time data plane verification. Evaluations of the data plane verification system based on TOBDD report 2-10x improvement over the state-of-the-art centralized data plane verifier.

Data plane verification can be an important technique to reduce network disruptions, and researchers have recently made significant progress in achieving fast data plane verification. However, as we apply existing data plane verification techniques to large-scale networks, two problems appear due to extremes. First, existing techniques cannot handle too-fast arrivals, which we call update storms, when a large number of data plane updates must be processed in a short time. Second, existing techniques cannot handle well too-slow arrivals, which we call long-tail update arrivals, when the updates from a number of switches take a long time to arrive.

A modern network needs to conduct a diverse set of tasks, and the existing approaches focus on developing specific tools for specific tasks, resulting in increasing complexity and lacking reusability. In this paper, we propose Flow Algebra as a unifying, easy-to-use framework to accomplish a large set of network management tasks. Based on the observation that relational databases based on relational algebra are well understood and widely used as a unifying framework for data management, we develop flow algebra based on relational algebra. On the other hand, flow tables, which are the fundamental data specifying the state of a network, cannot be stored in traditional relations, because of fundamental features such as wildcard and priorities. We define flow algebra based on novel, generalized relational operations that use equivalency to achieve efficient, unifying data store, query, and manipulation of both flow tables and traditional relations. We realize flow algebra with FlowDB and demonstrate its ease of use on diverse tasks. We further demonstrate that generality and ease-of-use do not need to come with a performance penalty. For example, for the well-studied network verification task, our system outperforms two state-of-the-art network verification engines, NoD and HSA, in their targeted domain, by 55x.

Network resource reservation systems are being developed and deployed, driven by the demand and substantial benefits of providing performance predictability for modern distributed applications. However, existing systems suffer limitations: They either are inefficient in finding the optimal resource reservation, or cause private information (e.g., from the network infrastructure) to be exposed (e.g., to the user). In this paper, we design BoxOpt, a novel system that leverages efficient oracle construction techniques in optimization and learning theory to automatically, and swiftly learn the optimal resource reservations without exchanging any private information between the network and the user. In BoxOpt, we first model the simple reservation interface adopted in most reservation systems as a resource membership oracle. Second, we develop an efficient algorithm that constructs a resource separation oracle by a linear number of calls on resource membership oracle. Third, we develop a generic framework to construct a resource optimization oracle by iteratively calling the resource separation oracle, and then develop three novel, efficient algorithms under this generic framework, the best of which computes the optimal resource reservation by a linear number of calls on resource separation oracle. As such, BoxOpt can discover the optimal resource reservation with O(n2) calls on the resource membership oracle. We implement a prototype of BoxOpt with and demonstrate its efficiency and efficacy via extensive experiments using real network topology and a 7-day trace from a large operational federation network. Results show that (1) BoxOpt has a 100% correctness ratio by comparing with a state-of-the-art optimization solver, and (2) for 90% of requests, BoxOpt learns the optimal resource reservation within 10 seconds.

End-to-end route control spanning a set of networks can provide opportunities to both end users to optimize interdomain control and network service providers to increase business offering. BGP, the de facto interdomain routing protocol, provides no programmable control. Recent proposals for interdomain control, such as MIRO, ARROW and SDX, provide more mechanisms and interfaces, but they are only either point or incremental solutions. In this paper, we provide the first, systematic formulation of the software-defined internetworking (SDI) model, in which a network exposes a programmable interface to allow clients to define the interdomain routes of the network, just as a traditional SDN switch exposes Openflow or another programmable interface to allow clients to define its next hops, extending SDN from intra-domain control to generic interdomain control. Different from intradomain SDN, which allows complete client control, SDI should also maximize network autonomy, such as by allowing a network to maintain the control of its interdomain export policies, to avoid fundamental violations such as valley routing. We define the optimal end-to-end SDI routing problem and conduct rigorous analysis to show that the problem is NP-hard. We develop a blackbox optimization algorithm, which leverages Bayesian optimization theory and important properties of interdomain routing algebra, to sample end-to-end routes sequentially and find a near-optimal policy-compliant end-to-end route with a small number of sample routes. We implement a prototype of our optimization algorithm and validate its effectiveness via extensive experiments using real interdomain network topology. Results show that in an interdomain network with over 60000 ASes and over 320000 AS-level links, in 80% experiment cases, the blackbox optimization algorithm can find a near-optimal policy-compliant end-to-end route by sampling less than 33 routes.

Software-Defined Networking (SDN) enables more dynamic and fine-grained network control. In particular, network operators can route traffic not only based on packet header fields, but also higher-level parameters such as user settings, traffic characteristics, and application-layer information extracted by virtualized network functions such as DPI, firewall and authentication servers. Integrating these higher-level parameters into an SDN programming framework brings substantial benefits but is still missing in the SDN community. In this paper, we articulate the challenges and then propose Trident, a novel unified SDN programming framework. Trident extends algorithmic SDN programming with a new abstraction called stream attribute, which integrates meta parameters into the match-action programming paradigm. Further, Trident adopts the idea of reactive value from function reactive programming, eliminating the complexity of manually handling dynamicity. To effectively and efficiently realize these novel ideas, Trident introduces reactive table as the basic processing unit and develops a domain-specific distributed update protocol to maintain consistency during updates. Evaluations show that Trident puts very little overhead on integrating existing network management tools and network functions, and can handle up to O(105) routing requests per second with O(100) milliseconds latency.

As modern network applications (e.g., large data analytics) become more distributed and can conduct application-layer traffic adaptation, they demand better network visibility to better orchestrate their data flows. As a result, the ability to predict the available bandwidth for a set of flows has become a fundamental requirement of today's networking systems. While there are previous studies addressing the case of non-reactive flows, the prediction for reactive flows, e.g., flows managed by TCP congestion control algorithms, still remains an open problem. In this paper, we take the first step to solving this problem in a data center network. To address both theoretical and practical challenges, we introduce a novel learning-based prediction system based on the NUM model, with two key techniques named fast factor learning (FFL) and efficient flow sampling. We adopt novel techniques to overcome practical concerns such as scalability, convergence and unknown system parameters. A system, Prophet, is proposed leveraging the emerging technologies of Software Defined Networking (SDN) to realize the model. Evaluations demonstrate that our solution achieves significant accuracy in a wide range of settings.

The ability to support continuous network configuration updates is an important ability for enabling Software Defined Networks (SDN) to handle frequent or bursty changes. Current solutions for updating SDN configurations focus on one single update at a time, leading to slow, sequential (i.e., blocking) update execution. In this paper, we develop update algebra, a novel, systematic, theoretical framework based on abstract algebra, to enable continuous, non-blocking, fast composition of multiple updates. Specifically, by modeling each data-plane operation in the set of data-plane operations to be executed by an update as a set-theoretical projection, update algebra defines novel operation composition so that the number of projections for the same match remains constant regardless of the number of updates to be composed, leading to substantial performance benefits. Specifying the dependencies of the data-plane operations in updates as a subset of a free monoid in the general case and as partial ordering for basic consistency, update algebra defines update composition that preserves consistency, even under partially-executed updates, to guarantee correctness. We conduct asymptotic analysis, extensive benchmarking using a real controller, and integration with a real application to demonstrate the benefits of update algebra. In particular, our asymptotic analysis demonstrates that in independent-update dominant settings, update completion time of update algebra remains asymptotically constant despite growth of the number of updates to be executed. Our benchmarking shows that update algebra can achieve 16x reduction in update latency even in settings with an update arrival rate of only 1. 6/s. Our integration with Hedera, a real SDN traffic engineering application, shows that update algebra can reduce average link bandwidth utilization by 30% compared with sequential updates.

Existing software-defined SDx architectures highly depend on a centralized control plane and hence can face substantial reliability challenges in software-defined coalition (SDC) settings, in which the centralized control plane can be weakly connected to the data plane, or even disconnected from the data plane due to high dynamicity. On the contrary, distributed control planes (e.g., OLSRv2) provide autonomy but lose flexibility and global policy guarantees. In this paper, we present Magnalium, a novel system to achieve high reliability in SDC networks by composing multiple control planes in real-time. Magnalium introduces a novel, unified composition framework that uses a distributed verification to systematically generate forwarding rules in accordance with desired policy requirements. Magnalium also introduces several supporting components to address challenges in wireless environment and resource management. We conduct data-driven simulations, showing that Magnalium benefits from both centralized and distributed control planes and even reduces downtime by 65% over the most reliable individual control plane.

Multi-domain network resource reservation systems are being deployed, driven by the demand and substantial benefits of providing predictable network resources. However, a major lack of existing systems is their coarse granularity, due to the participating networks' concern of revealing sensitive information, which can result in substantial inefficiencies. This paper presents Mercator, a novel multi-domain network resource discovery system to provide fine-grained, global network resource information, for collaborative sciences. The foundation of Mercator is a resource abstraction through algebraic-expression enumeration (i.e., linear inequalities/equations), as a compact representation of multiple properties of network resources (e.g., bandwidth, delay, and loss rate) in multi-domain networks. In addition, we develop an obfuscating protocol, to address the privacy concerns by ensuring that no participant can associate the algebraic expressions with the corresponding member networks. We also introduce a super-set projection technique to increase Mercator's scalability. We implement a prototype Mercator and deploy it in a small federation network. We also evaluate the performance of Mercator through extensive experiments using real topologies and traces. Results show that Mercator 1) efficiently discovers available networking resources in collaborative networks on average four orders of magnitude faster, and allows fairer allocations of network resources; 2) preserves the member networks' privacy with little overhead; and 3) scales to a collaborative network of 200 member networks.

Revealing an abstract view of the network is essential for the new paradigm of developing network-aware adaptive applications that can fully leverage the available computation and storage resources and achieve better business values. In this paper, we introduce ONV, a novel abstraction of flow-based on-demand network view. The ONV models network views as linear constraints on network-related variables in application-layer objective functions, and provides “equivalent” network views that allow applications to achieve the same optimal objectives as if they have the global information. We prove the lower bound for the number of links contained in an equivalent network view, and propose two algorithms to effectively calculate on-demand equivalent network views. We evaluate the efficacy and the efficiency of our algorithms extensively with real-world topologies. Evaluations demonstrate that the ONV can simplify the network up to 80% while maintaining an equivalent view of the network. Even for a large network with more than 25 000 links and a request containing 3000 flows, the result can be effectively computed in less than 1 min on a commodity server.

How to quickly and consistently update a network is among the most fundamental and common challenges in software defined networking (SDN) systems. Current approaches heavily rely on the (logically) centralized controller to initiate and orchestrate the network updates, resulting in long latency of update completion. In this paper, we present DDP, a system for fast, distributed network updates while preserving various consistency properties. The key technique in DDP is a novel primitive named datapath operation container (DOC), where each DOC is encoded with an individual operation and its dependency logic. DDP adopts the simple, but powerful DOCs to configure the network, so that network updates can be triggered and executed at the data plane in a distributed and local manner. Novel algorithms are designed to compute and optimize the DOCs for consistent updates. We implement DDP to evaluate its performance in various update scenarios. Experimental results show that DDP significantly improves network update speed by up to 52.1% for the real-time updates initiated by the controller, and further improves the speed by 55.6-61.4% for the updates directly triggered at the data plane, such as failure recovery.

As modern network applications (e.g., large data analytics) become more distributed and can conduct application-layer traffic adaptation, they demand better network visibility to better orchestrate their data flows. As a result, the ability to predict the available bandwidth for a set of flows has become a fundamental requirement of today's networking systems. While there are previous studies addressing the case of non-reactive flows, the prediction for reactive flows, e.g., flows managed by TCP congestion control algorithms, still remains an open problem. In this paper, we identify three challenges in providing throughput prediction for reactive flows: throughput dynamics, heterogeneous reactive control mechanisms, and source-constrained flows. Based on a previous theoretical model, we introduce a novel learning-based prediction system with a key component named fast factor learning (FFL) model. We adopt novel techniques to overcome practical concerns such as scalability, convergence and unknown system parameters. A system, Prophet, is proposed leveraging the emerging technologies of Software Defined Networking (SDN) to realize the model. Evaluations demonstrate that our solution achieves significant accuracy in a wide range of settings.

High-Ievel programming and programmable data paths are two key capabilities of software-defined networking (SDN). A fundamental problem linking these two capabilities is whether a given high-level SDN program can be realized onto a given low-level SDN datapath structure. Considering all high-level programs that can be realized onto a given datapath as the programming capacity of the datapath, we refer to this problem as the SDN data path programming capacity problem. In this paper, we conduct the first study on the SDN datapath programming capacity problem, in the general setting of high-level, datapath oblivious, algorithmic SDN programs and state-of-art multi-table SDN data path pipelines. In particular, considering datapath-oblivious SDN programs as computations and datapath pipelines as computation capabilities, we introduce a novel framework called SDN characterization junctions, to map both SDN programs and datapaths into a unifying space, deriving the first rigorous result on SDN datapath programming capacity. We not only prove our results but also conduct realistic evaluations to demonstrate the tightness of our analysis.

Software-defined networking (SDN) and network functions (NF) are two essential technologies that need to work together to achieve the goal of highly programmable networking. Unified SDN programming, which integrates states of network functions into SDN control plane programming, brings these two technologies together. In this paper, we conduct the first systematic study of unified SDN programming. We first show that integrating asynchronous, continuously changing states of network functions into SDN can introduce basic complexities. We then present Trident, a novel, unified SDN programming framework that introduces programming primitives including stream attributes, route algebra and live variables to remove these complexities. We demonstrate the expressiveness of Trident using realistic use cases and conduct an extensive evaluation of its efficiency.

As many applications today migrate to distributed computing and cloud platforms, their user experience depends heavily on network performance. Software Defined Networking (SDN) makes it possible to obtain a global view of the network, introducing the new paradigm of developing adaptive applications with network views. A naive approach of realizing the paradigm, such as distributing the whole network view to applications, is not practical due to scalability and privacy concerns. Existing approaches providing network abstractions are limited to special cases, such as bottlenecks exist only at networks edges, resulting in potentially suboptimal or infeasible decisions. In this paper, we introduce a novel, on-demand network abstraction service that provides an abstract network view supporting not only accurate end-to-end QoS metrics, which satisfy the requirements of many peer-to-peer applications, but also multi-flow correlation, which is essential for bandwidth-sensitive applications containing many flows to conduct global network optimization. We prove that our abstract view is equivalent to the original network view, in the sense that applications can make the same optimal decision as with the complete information. Our evaluations demonstrate that the abstraction guarantees feasibility and optimality for network optimizations and protects the network service providers' privacy. Our evaluations also show that the service can be implemented efficiently; for example, for an extreme large network with 30,000 links and abstraction requests containing 3,000 flows, an abstract network view can be computed in less than one second.

Providing an interface for network applications to access network state, Software-Defined Networking (SDN) northbound API protocol is the foundation for the development of programmable networks with adaptive applications. However, with the growing network scale and applications' need for routing state at multi-domain level, feeding complete routing states to applications would jeopardize their scalability and network providers' privacy. Thus a good routing state abstraction is needed, which must be on-demand so that different applications can receive customized abstract state suiting their needs. Moreover, it must be minimal and equivalent, i.e., containing all the necessary information for applications to make decisions as the complete state does with no redundancy. Current routing state abstractions are not on-demand, and adopt extreme aggregation approaches (e.g., the big switch) to provide a minimal abstraction with the price of severe information loss. For instance, bottleneck links shared between flows are concealed, leading applications to make sub-optimal decisions. In this paper, we design ORSAP, the first on-demand routing state abstraction protocol, through which network applications can describe their demands while Internet service providers can provide the on-demand minimal equivalent routing state accordingly. ORSAP ensures applications' scalability, protects network providers' privacy, and significantly reduces the traffic to disseminate the information. Experiments show that with ORSAP and the abstraction engine we introduced in this paper, one can achieve a state abstraction ratio of up to 60% with an extremely low computation time even with large networks and complex application queries.

Handling state dependencies is a major challenge in modern SDN programming, but existing frameworks do not provide sufficient abstractions nor tools to address this challenge. In this paper, we propose a novel, high-level programming abstraction and implement the *Function Automation SysTem (FAST)*. With the two key features, i.e., *automated state dependency tracking* and *efficient re-execution scheduling*, we demonstrate that FAST substantially simplifies state-dependent SDN programming and boosts the performance.

Despite the emergence of multi-table pipelining as a key feature of next-generation SDN data-path models, there is no existing work that addresses the substantial programming challenge of utilizing multi-tables automatically. In this paper, we present Magellan, the first system that addresses the aforementioned challenge. Introducing two novel, substantial algorithms, map-explore and table-design, Magellan achieves automatic derivation and population of multi-table pipelines from a datapath-oblivious, high-level SDN program written in a general-purpose language. Comparing the flow tables generated by Magellan with those produced by standard SDN controllers including OpenDaylight and Floodlight, we show that Magellan uses between 46-68x fewer rules.

Summary Over the past decade, content delivery networks (CDNs) have attracted substantial Internet traffic and improved quality of experience for Internet users. However, the evolution of the Internet ecosystem, which is driven by underlying economic incentives and ever emerging technologies, posts great challenges to the existing commercial CDNs (CCDNs). Thoroughly understanding the CDN industry from different aspects including market choice, technology, performance, tendency and infrastructure is indispensable to future Internet. In this paper, we conduct the first comprehensive study of China's CDNs using continuous, at‐scale, content‐driven measurements. Based on the massive amount of measurement data with multidimensional properties, we demystify the CCDNs in China and answer two important questions: (1) what is the development trend of CCDNs in China and (2) what are their unique characteristics. The answers to these questions have significant implications on CDN providers and users. Copyright © 2015 John Wiley & Sons, Ltd.

A major benefit of software-defined networking (SDN) over traditional networking is simpler and easier control of network devices. The diversity of SDN switch implementation properties, which include both diverse switch hardware capabilities and diverse control-plane software behaviors, however, can make it difficult to understand and/or to control the switches in an SDN network. In this paper, we present Tango, a novel framework to explore the issues of understanding and optimization of SDN control, in the presence of switch diversity. The basic idea of Tango is novel, simple, and yet quite powerful. In particular, different from all previous SDN control systems, which either ignore switch diversity or depend on that switches can and will report diverse switch implementation properties, Tango introduces a novel, proactive probing engine that infers key switch capabilities and behaviors, according to a well-structured set of Tango patterns, where a Tango pattern consists of a sequence of standard OpenFlow commands and a corresponding data traffic pattern. Utilizing the inference results from Tango patterns and additional application API hints, Tango conducts automatic switch control optimization, despite diverse switch capabilities and behaviors. Evaluating Tango on both hardware switches and emulated software switches, we show that Tango can infer flow table sizes, which are key switch implementation properties, within less than 5% of actual values, despite diverse switch caching algorithms, using a probing algorithm that is asymptotically optimal in terms of probing overhead. We demonstrate cases where routing and scheduling optimizations based on Tango improves the rule installation time by up to 70% in our hardware switch testbed.

The emergence of new capabilities such as virtualization and elastic (private or public) cloud computing infrastructures has made it possible to deploy multiple applications, on demand, on the same cloud infrastructure. A major challenge to achieve this possibility, however, is that modern applications are typically distributed, structured systems that include not only computational and storage entities, but also policy entities (e.g., load balancers, firewalls, intrusion prevention boxes). Deploying applications on a cloud infrastructure without the policy entities may introduce substantial policy violations and/or security holes. In this paper, we present PACE: the first systematic framework for Policy-Aware Application Cloud Embedding. We precisely define the policy-aware, cloud application embedding problem, study its complexity and introduce simple, efficient, online primal-dual algorithms to embed applications in cloud data centers. We conduct evaluations using data from a real, large campus network and a realistic data center topology to evaluate the feasibility and performance of PACE. We show that deployment in a cloud without considering in-network policies may lead to a large number of policy violations (e.g., using tree routing as a way to enforce in-network policies may observe up to 91% policy violations). We also show that our embedding algorithms are very efficient by comparing with a good online fractional embedding algorithm.

Software-Defined Networking offers the appeal of a simple, centralized programming model for managing complex networks. However, challenges in managing low-level details, such as setting up and maintaining correct and efficient forwarding tables on distributed switches, often compromise this conceptual simplicity. In this pa- per, we present Maple, a system that simplifies SDN programming by (1) allowing a programmer to use a standard programming language to design an arbitrary, centralized algorithm, which we call an algorithmic policy, to decide the behaviors of an entire network, and (2) providing an abstraction that the programmer-defined, centralized policy runs, conceptually, "afresh" on every packet entering a network, and hence is oblivious to the challenge of translating a high-level policy into sets of rules on distributed individual switches. To implement algorithmic policies efficiently, Maple includes not only a highly-efficient multicore scheduler that can scale efficiently to controllers with 40+ cores, but more importantly a novel tracing runtime optimizer that can automatically record reusable policy decisions, offload work to switches when possible, and keep switch flow tables up-to-date by dynamically tracing the dependency of policy decisions on packet contents as well as the environment (system state). Evaluations using real HP switches show that Maple optimizer reduces HTTP connection time by a factor of 100 at high load. During simulated benchmarking, Maple scheduler, when not running the optimizer, achieves a throughput of over 20 million new flow requests per second on a single machine, with 95-percentile latency under 10 ms.

P2P platforms have been criticized because of the heavy strain that they can inflict on costly inter-domain links of network operators. It is therefore mandatory to develop network optimization schemes for controlling the load generated by a P2P platform on an operator network. While many research efforts exist on centralized tracker-based systems, in recent years multiple DHT-based P2P platforms have been widely deployed and considered as commercial services due to their scalability and fault tolerance. Finding network optimization for DHT-based P2P applications has thereby potential large practical impacts. In this paper, we present THash, a simple scheme that implements a distributed and effective network optimization for DHT systems. THash uses standard DHT put/get semantics and utilizes a triple hash method to guide the DHT clients to choose their sharing peers in proper domains. We have implemented THash in a major commercial P2P system (PPLive), using the standard ALTO/P4P protocol as the network information source. We conducted experiments over this network in real operation and observed that compared with Native DHT, THash reduced respectively by 47.4% and 67.7% the inter-PID and inter-AS traffic, while reducing the average downloading time by 14.6% to 24.5%.

P2P platforms have been criticized because of the heavy strain that some P2P services can inflict on costly inter-domain links of network operators. It is therefore necessary to develop network optimization schemes for controlling the load generated by P2P platforms on an operator network. Previous focus on network optimization has been mostly on centralized tracker-based systems. However, in recent years multiple DHT-based P2P networks are widely deployed due to their scalability and fault tolerance, and these networks have even been considered as platforms for commercial services. Thereby, finding network optimization for DHT-based P2P applications has potentially large practical impacts. In this paper, we present THash, a simple scheme to implement an effective distributed network optimization for DHT systems. THash is based on standard DHT put/get semantics and utilizes a triple hash method to guide the DHT clients sharing resources with peers in proper domains. We have implemented THash in a major P2P application (PPLive) by using the standard ALTO/P4P protocol as the network information source. We conducted realistic experiments over the network and observed that compared with Native DHT, THash only generated 45.5% and 35.7% of inter-PID and inter-AS traffic, and at the same time shortened the average downloading time by 13.8% to 22.1%.

Cloud computing is an increasingly important solution for providing services deployed in dynamically scalable cloud networks. Services in the cloud computing networks may be virtualized with specific servers which host abstracted details. Some of the servers are active and available, while others are busy or heavy loaded, and the remaining are offline for various reasons. Users would expect the right and available servers to complete their application requirements. Therefore, in order to provide an effective control scheme with parameter guidance for cloud resource services, failure detection is essential to meet users' service expectations. It can resolve possible performance bottlenecks in providing the virtual service for the cloud computing networks. Most existing Failure Detector (FD) schemes do not automatically adjust their detection service parameters for the dynamic network conditions, thus they couldn't be used for actual application. This paper explores FD properties with relation to the actual and automatic fault-tolerant cloud computing networks, and find a general non-manual analysis method to self-tune the corresponding parameters to satisfy user requirements. Based on this general automatic method, we propose specific and dynamic Self-tuning Failure Detector, called SFD, as a major breakthrough in the existing schemes. We carry out actual and extensive experiments to compare the quality of service performance between the SFD and several other existing FDs. Our experimental results demonstrate that our scheme can automatically adjust SFD control parameters to obtain corresponding services and satisfy user requirements, while maintaining good performance. Such an SFD can be extensively applied to industrial and commercial usage, and it can also significantly benefit the cloud computing networks.

Multi-user multiple-input multiple-output theory predicts manyfold capacity gains by leveraging many antennas on wireless base stations to serve multiple clients simultaneously through multi-user beamforming (MUBF). However, realizing a base station with a large number antennas is non-trivial, and has yet to be achieved in the real-world. We present the design, realization, and evaluation of Argos, the first reported base station architecture that is capable of serving many terminals simultaneously through MUBF with a large number of antennas (M >> 10). Designed for extreme flexibility and scalability, Argos exploits hierarchical and modular design principles, properly partitions baseband processing, and holistically considers real-time requirements of MUBF. Argos employs a novel, completely distributed, beamforming technique, as well as an internal calibration procedure to enable implicit beamforming with channel estimation cost independent of the number of base station antennas. We report an Argos prototype with 64 antennas and capable of serving 15 clients simultaneously. We experimentally demonstrate that by scaling from 1 to 64 antennas the prototype can achieve up to 6.7 fold capacity gains while using a mere 1/64th of the transmission power.

Many large content publishers use multiple content distribution networks to deliver their content, and many commercial systems have become available to help a broader set of content publishers to benefit from using multiple distribution networks, which we refer to as content multihoming. In this paper, we conduct the first systematic study on optimizing content multihoming, by introducing novel algorithms to optimize both performance and cost for content multihoming. In particular, we design a novel, efficient algorithm to compute assignments of content objects to content distribution networks for content publishers, considering both cost and performance. We also design a novel, lightweight client adaptation algorithm executing at individual content viewers to achieve scalable, fine-grained, fast online adaptation to optimize the quality of experience (QoE) for individual viewers. We prove the optimality of our optimization algorithms and conduct systematic, extensive evaluations, using real charging data, content viewer demands, and performance data, to demonstrate the effectiveness of our algorithms. We show that our content multihoming algorithms reduce publishing cost by up to 40%. Our client algorithm executing in browsers reduces viewer QoE degradation by 51%.

As live streaming networks grow in scale and complexity, they are becoming increasingly difficult to evaluate. Existing evaluation methods including lab/testbed testing, simulation, and theoretical modeling, lack either scale or realism. The industrial practice of gradually-rolling-out in a testing channel is lacking in controllability and protection when experimental algorithms fail, due to its passive approach. In this paper, we design a novel system called ShadowStream that introduces evaluation as a built-in capability in production Internet live streaming networks. ShadowStream introduces a simple, novel, transparent embedding of experimental live streaming algorithms to achieve safe evaluations of the algorithms during large-scale, real production live streaming, despite the possibility of large performance failures of the tested algorithms. ShadowStream also introduces transparent, scalable, distributed experiment orchestration to resolve the mismatch between desired viewer behaviors and actual production viewer behaviors, achieving experimental scenario controllability. We implement ShadowStream based on a major Internet live streaming network, build additional evaluation tools such as deterministic replay, and demonstrate the benefits of ShadowStream through extensive evaluations.

Physical layer techniques have come a long way and can achieve very close to Shannon capacity for point-to-pint links. It is apparent that, to further improve network capacity significantly, we have to resort to concurrent transmissions. Many concurrent transmission techniques (e.g., zero forcing, interference alignment and distributed MIMO) are proposed in which multiple senders jointly encode signals to multiple receivers so that interference is aligned and each receiver is able to decode its desired information. In this paper, we investigate the constraints and challenges of using interference alignment. Our main contribution is conducting the first systematic investigation on the key issue of identifying opportunities for interference alignment. We identify diverse, novel scenarios for using interference alignment. We show that identifying opportunities for interference alignment in the general case is computational challenging. However, we also present a promising, distributed algorithm for identifying a wide range of opportunities for interference alignment using a unifying framework based on the degree of freedom. Our second contribution is evaluating key practical implementation issues.

Collisions in overlapping channels can be a major problem in the deployment of high-speed OFDM networks. In this paper, we present Remap, a simple, novel paradigm for handling collisions in overlapping OFDM channels. Remap introduces a novel concept of retransmission permutation that permutes the bit-to-subcarrier assignment after each transmission, departing from the traditional, simply-repeat paradigm. Remap is simple to implement and able to exploit collision-free subcarriers to decode frames despite successive collisions in overlapping channels. We apply Remap to 802.11g to demonstrate that the diversity created by remapped frames can substantially improve decoding efficiency and improve wireless throughput. We implement our technique in software radio and demonstrate that it has potential to be deployed with simple software and firmware updates.

Network resiliency is crucial to IP network operations. Existing techniques to recover from one or a series of failures do not offer performance predictability and may cause serious congestion. In this paper, we propose Resilient Routing Reconfiguration (R3), a novel routing protection scheme that is (i) provably congestion-free under a large number of failure scenarios; (ii) efficient by having low router processing overhead and memory requirements; (iii) flexible in accommodating different performance requirements (e.g., handling realistic failure scenarios, prioritized traffic, and the trade-off between performance and resilience); and (iv) robust to both topology failures and traffic variations. We implement R3 on Linux using a simple extension of MPLS, called MPLS-ff. We then conduct extensive Emulab experiments and simulations using realistic network topologies and traffic demands. Our results show that R3 achieves near-optimal performance and is at least 50% better than the existing schemes under a wide range of failure scenarios.

We present muNet, a wireless mesh network design and implementation to harness the multiuser capacity of wireless channels. Traditionally, media access control is designed to schedule one transmission between one sender and one receiver without interference at any given time. However, this design is suboptimal in terms of achieving the multiuser capacity of multi-access wireless channels. In muNet, we implement effective physical layer techniques called superposition coding and successive interference cancellation to enable simultaneous unicast transmissions from a single transmitter to multiple receivers as well as from multiple transmitters to a single receiver. We design the first practical MAC protocol that leverages such a physical layer and exposes the multiuser capacity to upper layers. We also present a simple, effective routing protocol that increases simultaneous transmission opportunities for the MAC layer. A proof-of-concept muNet is implemented on the GNU radio platform. Measurements on the implementation shows that the throughput gains of muNet are significant (up to 93%).

Due to recent large-scale deployments of delay and loss-sensitive applications, there are increasingly stringent demands on the monitoring of service level agreement metrics. Although many end-to-end monitoring methods have been proposed, they are mainly based on active probing and thus inject measurement traffic into the network. In this paper, we propose a new scheme for monitoring service level agreement metrics, in particular, delay distribution. Our scheme is passive and therefore will not cause perturbation to real traffic. Using realistic delay and traffic demands, we show that our scheme achieves high accuracy and can detect burst events that will be missed by probing based methods.

A major barrier for the adoption of wireless mesh networks is severe limits on throughput. Many in-network packet mixing techniques at the network layer [1], [2], [3] as well as the physical layer [4], [5], [6] have been shown to substantially improve throughput. However, the optimal mixing algorithm that maximizes throughput is still unknown. We propose iPack, an algorithm for in-network generation of composite packets that integrates coding at two different layers of the protocol stack: XOR-based network coding and physical layer superposition coding. Using extensive simulations, we find that the throughput gain of the joint coding iPack algorithm is 30% more than the better performer of network coding and superposition coding in a wide range of scenarios, and automatically takes advantage of the best available coding opportunities. In a typical wireless mesh network when more traffic is between the clients and access points, the average throughput improvement of iPack, our joint optimization scheduler, can be 324%, while there can be little gain (less than 10%) if network coding alone is used. We also validate our results by implementing iPack on a small-scale testbed based on GNU Radio.

IP network mobility is emerging as a major paradigm for providing continuous Internet access while a set of users are on the move in a transportation system. The intense interest on its support has led to the establishment of the NEMO IETF working group and a test-deployment by a major airline equipment vendor - Boeing - on major airline routes. However, the previously proposed solutions are either inefficient or may cause instability to the global Internet. We propose WINMO, a simple, systematic, novel solution for wide-area IP network mobility using techniques including route aggregation, scoped update propagation, and packet mobility states. Our solution provides efficient routing when users travel both across autonomous systems (ASes) and within a single AS, generates minimal global routing overhead to prevent global instability, ensures good location privacy, and helps to defend against denial-of-service attacks. Furthermore, our basic scheme (without packet mobility state) is transparent to both clients and servers. Our extensive evaluations demonstrate the effectiveness of our mobility solution.

In multi-rate wireless LANs, throughput-based fair bandwidth allocation can lead to drastically reduced aggregate throughput. To balance aggregate throughput while serving users in a fair manner, proportional fair or time-based fair scheduling has been proposed to apply at each access point (AP). However, since a realistic deployment of wireless LANs can consist of a network of APs, this paper considers proportional fairness in this much wider setting. Our technique is to intelligently associate users with APs to achieve optimal proportional fairness in a network of APs. We propose two approximation algorithms for periodical offline optimization. Our algorithms are the first approximation algorithms in the literature with a tight worst-case guarantee for the NP-hard problem. Our simulation results demonstrate that our algorithms can obtain an aggregate throughput which can be as much as 2.3 times more than that of the max-min fair allocation in 802.11b. While maintaining aggregate throughput, our approximation algorithms outperform the default user-AP association method in the 802.11b standard significantly in terms of fairness.

Inference of the routing topology and link performance from a node to a set of other nodes is an important component of network monitoring and application design. In this paper we propose a general framework for designing topology inference algorithms based on additive metrics. Our framework allows the integration of both end-to-end packet probing measurements and traceroute type measurements. Based on this framework we design several computationally efficient topology inference algorithms. In particular, we propose a novel sequential topology inference algorithm to address the probing scalability problem and handle dynamic node joining and leaving. We provide sufficient conditions for the correctness of our algorithms and derive lower bounds on the probability of correct topology inference. We conduct Internet experiments to evaluate and demonstrate the effectiveness of our algorithms.

User-contributed wireless mesh networks are a disruptive technology that may fundamentally change the economics of edge network access and bring the benefits of a computer network infrastructure to local communities at low cost, anywhere in the world. To achieve high throughput despite highly unpredictable and lossy wireless channels, it is essential that such networks take advantage of transmission opportunities wherever they emerge. However, as opportunistic routing departs from the traditional but less effective deterministic, shortest-path based routing, user nodes in such networks may have less incentive to follow protocols and contribute. In this paper, we present the first routing protocols in which it is incentive-compatible for each user node to honestly participate in the routing despite opportunistic transmissions. We not only rigorously prove the properties of our protocols but also thoroughly evaluate a complete implementation of our protocols. Experiments show that there is a 5.8%-58.0% gain in throughput when compared with an opportunistic routing protocol that does not provide incentives and users can act selfishly.

Configurations for today's IP networks are becoming increasingly complex. As a result, configuration management is becoming a major cost factor for network providers and configuration errors are becoming a major cause of network disruptions. In this paper, we present and evaluate the novel idea of shadow configurations. Shadow configurations allow configuration evaluation before deployment and thus can reduce potential network disruptions. We demonstrate using real implementation that shadow configurations can be implemented with low overhead.

A major barrier for the adoption of wireless mesh networks is severe limits on throughput. In this paper, we apply superposition coding to substantially improve network capacity of large, dense wireless mesh networks. Superposition coding is a physical layer technique that allows a transmitter to simultaneously send independent packets to multiple receivers. While superposition coding has been studied extensively by the physical layer community, we present the first design of practical and effective MAC protocols to take advantage of superposition coding in wireless mesh networks. Extensive evaluations show that superposition coding can be a practical method to increase the throughput of large, dense wireless mesh networks. Specifically, in a mesh network with 2 to 64 active receivers and one gateway, we show that our system can increase throughput up to 154%, with average gain ranging from 10% to 21%. When there are multiple gateways forming a mesh network, our system gains up to 98%, with average gain ranging from 24% to 46%. These results clearly demonstrate the potential benefits of our system. We also present results from an implementation of superposition coding using GNU Radio.

Reliability is a critical requirement of the Internet. The availability and resilience of the Internet under failures can have significant global effects. However, in the current Internet routing architecture, achieving the high level of reliability demanded by many mission critical activities can be costly. In this paper, we first propose a novel solution framework called reliability as an interdomain service (REIN) that can be incrementally deployed in the Internet and may improve the redundancy of IP networks at low cost. We then present robust algorithms to efficiently utilize network redundancy to improve reliability. We use real IP network topologies and traffic traces to demonstrate the effectiveness of our framework and algorithms.

Overlay networks have emerged as a generic networking paradigm to improve network performance and construct new applications. Although many overlay algorithms have been proposed lately, they tend to focus on a single overlay, without considering how to share network capacity with other traffic and other overlays. In this paper, we study optimal capacity sharing of network with multiple overlays. We first formulate the problem of optimal capacity sharing of networks with multiple overlays as a nonlinear optimization problem. We show that traditional flow-level rate controllers result in sub-optimal sharing results between the different overlays. We design efficient and distributed overlay flows control algorithms and demonstrate the effectiveness of our design

Determining node positions is essential for many next-generation network functionalities. Previous localization algorithms lack correctness guarantees or require network density higher than required for unique localizability. In this paper, we describe a class of algorithms for fine-grained localization called Sweeps. Sweeps correctly finitely localizes all nodes in bilateration networks. Sweeps also handles angle measurements and noisy measurements. We demonstrate the practicality of our algorithm through extensive simulations on a large number of networks, upon which it consistently localizes one-thousand-node networks of average degree less than five in less than two minutes on a consumer PC.

Traffic engineering plays a critical role in determining the performance and reliability of a network. A major challenge in traffic engineering is how to cope with dynamic and unpredictable changes in traffic demand. In this paper, we propose COPE, a class of traffic engineering algorithms that optimize for the expected scenarios while providing a worst-case guarantee for unexpected scenarios. Using extensive evaluations based on real topologies and traffic traces, we show that COPE can achieve efficient resource utilization and avoid network congestion in a wide variety of scenarios.

In this paper, we provide a theoretical foundation for the problem of network localization in which some nodes know their locations and other nodes determine their locations by measuring the distances to their neighbors. We construct grounded graphs to model network localization and apply graph rigidity theory to test the conditions for unique localizability and to construct uniquely localizable networks. We further study the computational complexity of network localization and investigate a subclass of grounded graphs where localization can be computed efficiently. We conclude with a discussion of localization in sensor networks where the sensors are placed randomly.

We present a general model of interdomain route selection to study interdomain traffic engineering. In this model, the routing of multiple destinations can be coordinated. Thus the model can capture general traffic engineering behaviors such as load balancing and link capacity constraints. We first identify potential routing instability and inefficiency of interdomain traffic engineering. We then derive a sufficient condition to guarantee convergence. We also show that the constraints on local policies imposed by business considerations in the Internet can guarantee stability without global coordination. Using realistic Internet topology, we evaluate the extent to which routing instability of interdomain traffic engineering can happen when the constraints are violated.

The recent discovery of instability caused by the interaction of local routing policies of multiple ASes has led to extensive research on the subject. However, previous studies analyze stability under a specific route selection algorithm. In this paper, instead of studying a specific route selection algorithm, we study a general class of route selection algorithms which we call rational route selection algorithms. We present a sufficient condition to guarantee routing convergence in a heterogeneous network where each AS runs any rational route selection algorithm. Applying our general results, we study the potential instability of a network where the preference of an AS depends on not only its egress routes to the destinations but also its inbound traffic patterns (i.e., the distribution of incoming traffic from its neighbors). We show that there exist networks which will have persistent route oscillations even when the ASes strictly follow the constraints imposed by business considerations, and adopt any rational route selection algorithms.

Knowing the positions of the nodes in a network is essential to many next generation pervasive and sensor network functionalities. Although many network localization systems have recently been proposed and evaluated, there has been no systematic study of partially localizable networks, i.e., networks in which there exist nodes whose positions cannot be uniquely determined. There is no existing study which correctly identifies precisely which nodes in a network are uniquely localizable and which are not. This absence of a sufficient uniqueness condition permits the computation of erroneous positions that may in turn lead applications to produce flawed results. In this paper, in addition to demonstrating the relevance of networks that may not be fully localizable, we design the first framework for two dimensional network localization with an efficient component to correctly determine which nodes are localizable and which are not. Implementing this system, we conduct comprehensive evaluations of network localizability, providing guidelines for both network design and deployment. Furthermore, we study an integration of traditional geographic routing with geographic routing over virtual coordinates in the partially localizable network setting. We show that this novel cross-layer integration yields good performance, and argue that such optimizations will be likely be necessary to ensure acceptable application performance in partially localizable networks.

Multihoming is a popular method used by large enterprises and stub ISPs to connect to the Internet to reduce cost and improve performance. Recently researchers have studied the potential benefits of multihoming and proposed protocols and algorithms to realize these benefits. They focus on how to dynamically select which ISPs to use for forwarding and receiving packets, and assume that the set of subscribed ISPs is given a priori. In practice, a user often has the freedom to choose which subset of ISPs among all available ISPs to subscribe to. We call the problem of how to choose the optimal set of ISPs the ISP subscription problem. In this paper, We design a dynamic programming algorithm to solve the ISP subscription problem optimally. We also design a more efficient algorithm for a large class of common pricing functions. Using real traffic traces and realistic pricing data, we show that our algorithm reduces users' cost. Next we study how ISPs respond to users' optimal ISP subscription by adjusting their pricing strategies. We call this problem the ISP pricing problem. Using a realistic charging model, we formulate the problem as a non-cooperative game. We first prove that if cost is the only criterion used by a user to determine which subset of ISPs to subscribe to, at any equilibrium all ISPs receive zero revenue. We then study a more practical formulation in which different ISPs provide different levels of reliability and users choose ISPs to both improve reliability and reduce cost. We analyze this problem and show that at any equilibrium an ISP's revenue is positive and determined by its reliability.

In many applications, wireless ad-hoc networks are formed by devices belonging to independent users. Therefore, a challenging problem is how to provide incentives to stimulate cooperation. In this paper, we study ad-hoc games---the routing and packet forwarding games in wireless ad-hoc networks. Unlike previous work which focuses either on routing or on forwarding, this paper investigates both routing and forwarding. We first uncover an impossibility result---there does not exist a protocol such that following the protocol to always forward others' traffic is a dominant action. Then we define a novel solution concept called cooperation-optimal protocols. We present Corsac, a cooperation-optimal protocol consisting of a routing protocol and a forwarding protocol. The routing protocol of Corsac integrates VCG with a novel cryptographic technique to address the challenge in wireless ad-hoc networks that a link's cost (ie, its type) is determined by two nodes together. Corsac also applies efficient cryptographic techniques to design a forwarding protocol to enforce the routing decision, such that fulfilling the routing decision is the optimal action of each node in the sense that it brings the maximum utility to the node. Additionally, we extend our framework to a practical radio propagation model where a transmission is successful with a probability. We evaluate our protocols using simulations. Our evaluations demonstrate that our protocols provide incentives for nodes to forward packets.

Recently we have seen an emergent trend of self adaptive routing in both Internet and wireless ad hoc networks. Although there are previous methods for computing the traffic equilibria of self adaptive routing (e.g., selfish routing), these methods use computationally demanding algorithms and require that a precise analytical model of the network be given. Also, it remains an open question how to design an adaptive routing scheme which ensures convergence to traffic equilibria in practice. In this paper we propose a simple, efficient, distributed probabilistic routing scheme for self adaptive routing in dynamic, realistic environments. Using both analysis and extensive simulations, we show that our scheme can converge to the desired traffic equilibrium (either user-optimal or network-optimal) very quickly. We find that user-optimal routing can achieve very close to optimal average latency in dynamic environments, but such performance often comes at the cost of seriously overloading certain links. To avoid link overloads, we improve adaptive routing by optimizing average user latency and link utilization simultaneously. Our evaluation shows that there is a trade-off between optimizing dual objectives, but the degradation in average latency is only marginal for typical link utilization requirements.

We provide a theoretical foundation for the problem of network localization in which some nodes know their locations and other nodes determine their locations by measuring the distances to their neighbors. We construct grounded graphs to model network localization and apply graph rigidity theory to test the conditions for unique localizability and to construct uniquely localizable networks. We further study the computational complexity of network localization and investigate a subclass of grounded graphs where localization can be computed efficiently. We conclude with a discussion of localization in sensor networks where the sensors are placed randomly.

Multihoming is often used by large enterprises and stub ISPs to connect to the Internet. In this paper, we design a series of novel smart routing algorithms to optimize cost and performance for multihomed users. We evaluate our algorithms through both analysis and extensive simulations based on realistic charging models, traffic demands, performance data, and network topologies. Our results suggest that these algorithms are very effective in minimizing cost and at the same time improving performance. We further examine the equilibrium performance of smart routing in a global setting and show that a smart routing user can improve its performance without adversely affecting other users.

Mobile ad hoc networking has been an active research area for several years. How to stimulate cooperation among selfish mobile nodes, however, is not well addressed yet. In this paper, we propose Sprite, a simple, cheat-proof, credit-based system for stimulating cooperation among selfish nodes in mobile ad hoc networks. Our system provides incentive for mobile nodes to cooperate and report actions honestly. Compared with previous approaches, our system does not require any tamper-proof hardware at any node. Furthermore, we present a formal model of our system and prove its properties. Evaluations of a prototype implementation show that the overhead of our system is small. Simulations and analysis show that mobile nodes can cooperate and forward each other's messages, unless the resource of each node is extremely low.

A recent trend in routing research is to avoid inefficiencies in network-level routing by allowing hosts to either choose routes themselves (e.g., source routing) or use overlay routing networks (e.g., Detour or RON). Such approaches result in selfish routing, because routing decisions are no longer based on system-wide criteria but are instead designed to optimize host-based or overlay-based metrics. A series of theoretical results showing that selfish routing can result in suboptimal system behavior have cast doubts on this approach. In this paper, we use a game-theoretic approach to investigate the performance of selfish routing in Internet-like environments. We focus on intra-domain network environments and use realistic topologies and traffic demands in our simulations. We show that in contrast to theoretical worst cases, selfish routing achieves close to optimal average latency in such environments. However, such performance benefit comes at the expense of significantly increased congestion on certain links. Moreover, the adaptive nature of selfish overlays can significantly reduce the effectiveness of traffic engineering by making network traffic less predictable.

Several reputation systems have been proposed for mobile ad-hoc networks in order to stimulate cooperation among mobile nodes. However, whether or not the mobile nodes will agree on the reputation of other nodes is not studied. In this paper, we present a formal specification and analysis of a general class of mechanisms to locally update the reputation of mobile nodes. Given an initial assessment of the reputation of other mobile nodes, we formally show that under mild conditions, the mobile nodes will achieve reputation agreement. Our analysis captures reputation propagation using graph connectivity and makes use of a recent theoretical result [A. Jadbabaie, et. al., IEEE Control and Decision Conference, 2001]. We also evaluate the convergence speed of two reputation propagation mechanisms through simulations. Our simulations show that the speed of reputation propagation is an important factor for the convergence speed of reputation agreement.

We present the design and specification of a protocol for scalable and reliable group rekeying together with performance evaluation results. The protocol is based upon the use of key trees for secure groups and periodic batch rekeying. At the beginning of each rekey interval, the key server sends a rekey message to all users consisting of encrypted new keys (encryptions, in short) carried in a sequence of packets. We present a scheme for identifying keys, encryptions, and users, and a key assignment algorithm that ensures that the encryptions needed by a user are in the same packet. Our protocol provides reliable delivery of new keys to all users eventually. It also attempts to deliver new keys to all users with a high probability by the end of the rekey interval. For each rekey message, the protocol runs in two steps: a multicast step followed by a unicast step. Proactive forward error correction (FEC) multicast is used to reduce delivery latency. Our experiments show that a small FEC block size can be used to reduce encoding time at the server without increasing server bandwidth overhead. Early transition to unicast, after at most two multicast rounds, further reduces the worst-case delivery latency as well as user bandwidth requirement. The key server adaptively adjusts the proactivity factor based upon past feedback information; our experiments show that the number of NACKs after a multicast round can be effectively controlled around a target number. Throughout the protocol design, we strive to minimize processing and bandwidth requirements for both the key server and users.

We investigate the fairness, smoothness, responsiveness, and aggressiveness of TCP and three representative TCP-friendly congestion control protocols: GAIMD, TFRC, and TEAR. The properties are evaluated both analytically and via simulation by studying protocol responses to three network environment changes. The first environment change is the inherent fluctuations in a stationary network environment. Under this scenario, we consider three types of sending rate variations: smoothness, short-term fairness, and long-term fairness. For a stationary environment, we observe that smoothness and fairness are positively correlated. We derive an analytical expression for the sending rate coefficient of variation for each of the four protocols. These analytical results match well with experimental results. The other two environment changes we study are a step increase of network congestion and a step increase of available bandwidth. Protocol responses to these changes reflect their responsiveness and aggressiveness, respectively.

In secure group communications, users of a group share a common group key. A key server sends the group key to authorized new users as well as performs group rekeying for group users whenever the key changes. In this paper, we investigate scalability issues of reliable group rekeying, and provide a performance analysis of our group key management system (called keygem) based upon the use of key trees. Instead of rekeying after each join or leave, we use periodic batch rekeying to improve scalability and alleviate out-of-sync problems among rekey messages as well as between rekey and data messages. Our analyses show that batch rekeying can achieve large performance gains. We then investigate reliable multicast of rekey messages using proactive FEC. We observe that rekey transport has an eventual reliability and a soft real-time requirement, and that the rekey workload has a sparseness property, that is, each group user only needs to receive a small fraction of the packets that carry a rekey message sent by the key server. We also investigate tradeoffs between server and receiver bandwidth requirements versus group rekey interval, and show how to determine the maximum number of group users a key server can support.

Many emerging web and Internet applications are based on a group communications model. Thus, securing group communications is an important Internet design issue. The key graph approach has been proposed for group key management. Key tree and key star are two important types of key graphs. Previous work has been focused on individual rekeying, i.e., rekeying after each join or leave request. In this paper, we first identify two problems with individual rekeying: inefficiency and an out-of-sync problem between keys and data. We then propose the use of periodic batch rekeying which can improve efficiency and alleviate the out-of-sync problem. We devise a marking algorithm to process a batch of join and leave requests. We then analyze the key server's processing cost for batch rekeying. Our results show that batch rekeying, compared to individual rekeying, saves server cost substantially. We also show that when the number of requests in a batch is not large, the best key tree degree is four; otherwise, key star (a special key tree with root degree equal to group size) outperforms small-degree key trees. Keywords: Secure group communications, group key management, rekeying. 1.

Multicast sessions may have a large number of receivers with heterogeneous reception capacities. To accommodate this heterogeneity various multi-rate schemes, based upon the use of layering or replication, have been proposed. We consider the optimal partitioning of receivers into groups for multi-rate schemes. For a general class of utility functions, we formulate the partitioning problem as an optimization problem to maximize the sum of receiver utilities. We present an efficient dynamic programming algorithm to solve the partitioning problem, and prove that the solution it finds is optimal. We also show that the majority of the benefit of a multi-rate scheme can be gained by using a small number of groups (or layers), say 4 to 5. To illustrate our solution approach, we apply it to the case where receiver capacities are determined by multi-rate max-min fair rates. A complete protocol for receiver rates computation, rates collection, optimal receiver partitioning, and receiver adaptation is presented. We then compare our approach with other multi-rate approaches as well as a single-rate approach. Experimental results show that our approach provides substantial performance improvements.

Instead of the increase-by-one decrease-to-half strategy used in TCP for congestion window adjustment, we consider the general case such that the increase value and decrease ratio are parameters. That is, in the congestion avoidance state, the window size is increased by /spl alpha/ per window of packets acknowledged and it is decreased to /spl beta/ of the current value when there is congestion indication. We refer to this window adjustment strategy as general additive increase multiplicative decrease (GAIMD). We present the (mean) sending rate of a GAIMD flow as a function of /spl alpha/, /spl beta/, loss rate, mean round-trip time, mean timeout value, and the number of packets acknowledged by each ACK. We conducted extensive experiments to validate this sending rate formula. We found the formula to be quite accurate for a loss rate of up to 20%. We also present a simple relationship between /spl alpha/ and /spl beta/ for a GAIMD flow to be TCP-friendly, that is, for the GAIMD flow to have approximately the same sending rate as a TCP flow under the same path conditions. We present results from simulations in which TCP-friendly GAIMD flows (/spl alpha/=0.31, /spl beta/=7/8) compete for bandwidth with TCP Reno flows and with TCP SACK flows, on a DropTail link as well as on a RED link. We found that the GAIMD flows were highly, TCP-friendly. Furthermore, with /spl beta/ at 7/8 instead of 1/2, these GAIMD flows have reduced rate fluctuations compared to TCP flows.