We focus on the problem of efficient communications over access networks with asymmetric bandwidth and capability. We propose a resource-constrained asymmetric redundancy elimination algorithm (RCARE) to leverage downlink bandwidth and receiver capability to accelerate the uplink data transfer. RCARE can be deployed on a client or a proxy. Different from existing asymmetric algorithms, RCARE uses a flexible matching mechanism to identify redundant data and allocates a small sender cache to absorb the high downlink traffic overhead. Compared to existing redundancy elimination algorithms, RCARE provides a scalable sender cache that is adaptive based on resource and performance. We evaluate RCARE with real traffic traces collected from multiple servers and a campus gateway. The trace-driven simulation results indicate that RCARE achieves higher goodput gains and reduces downlink traffic compared to existing asymmetric communication algorithms. We design an adaptation algorithm for resource-constrained senders sending multiple data streams. Our algorithm takes samples from data streams and predicts how to invest cache size on individual data streams to achieve maximal uplink goodput gain. The adaptation algorithm improves the goodput gain by up to 87% compared to the baseline. In first 10% of data streams (sorted by the optimal goodput gains), RCARE achieves up to 42% goodput gain on average.

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.

IP multicast dictates high-end routers and incurs high administrative overhead, which prevent them from being deployed in many video streaming scenarios. In this paper, we study the problem of computing the multipath multicast routes for streaming videos in Software-Defined Networks (SDNs), which adopt less expensive switches and reduce administrative overhead for lower CAPEX/OPEX. The objectives of the considered problem are robustness, load balance, SDN compatibility, and adaptiveness. We formulate this routing problem into a mathematical optimization problem, and propose two algorithms to address this problem. We implement the proposed algorithms on a popular OpenFlow controller to demonstrate its practicality, and we conduct extensive experiments to evaluate the proposed algorithms. The experiment results clearly show the merits of our algorithms over the IP multicast, e.g., we observe: (i) frame loss rate reduction between 19% and 95%, (ii) video quality improvement between 4 dB and 15 dB, (iii) sink throughput increase between 25% and 66%, and (iv) maximal link utilization reduction between 15% and 50%. We also show the tradeoff between optimality and run time of the two proposed algorithms: one of them is more suitable for smaller and more static networks, and the other one is more suitable for larger and more dynamic networks.

We consider the problem of asymmetric communications, which are common in many access networks. We propose a new asymmetric communication algorithm, called CacheQuery, to leverage on the already deployed downlink bandwidth and receiver capability to accelerate the uplink data transfer from one or multiple senders to a receiver. The design of CacheQuery differs from all previous asymmetric communication algorithms in two ways: (i) CacheQuery supports more flexible matching mechanism to identify redundant packet payload and (ii) CacheQuery allocates a small sender cache to absorb the potentially high downlink traffic overhead incurred by asymmetric communications. The trace-driven simulations indicate that, compared to existing asymmetric communication algorithms, CacheQuery achieves higher uplink transfer speed, yet reduces downlink traffic overhead.

Asymmetric access networks with downlink bandwidth 10-1000 times higher than uplink bandwidth are common, and upgrading these links may not be economically feasible in many usage scenarios. In this paper, we design, implement, and evaluate a parameterized Asymmetric Communication Layer (ACL) protocol that capitalizes the otherwise idling downlink bandwidth to boost the uplink goodput. The ACL protocol is different from existing techniques such as caching, protocol-independent redundancy elimination, WAN optimization, and online compression algorithms, because the ACL protocol is the first concrete network protocol to increase uplink goodput using downlink bandwidth. We implement the ACL protocol in ns-2 simulator, and conduct extensive simulations using synthetic traffic traces. The simulation results show the potential of the ACL protocol: compared to plain TCP/IP, 40-90% uplink goodput gain is possible. Users can also trade the goodput gain for lower delivery delay, as low as 1 RTT, or lower downlink payload amount, as low as 2.13 times of the actual data size. We also conduct a trace-driven simulation using a one-week real traffic trace of a Web server. We observe 24% uplink goodput gain, which shows the practicality of the ACL protocol.

Advanced packet processing in the data path of networks is common in the current Internet and is expanding to next-generation networks. Dynamic composition of such "network services" allows networks to establish connections with customized communication characteristics to satisfy various application requirements. In these networks, there are two problems that need to be solved: finding the optimal composition of services to satisfy the communication requirements of a given connection ("service composition") and finding the optimal path for a given composition of services such that the required services are executed in sequence along the path ("service routing"). So far, these two problems have been studied separately. In our work, we combine both into a "service composition and routing" approach that can achieve better solutions than the current, separate approach. We present a novel decision making system that can determine the optimal or near-optimal solutions for the service composition and routing problem. We develop a synthetic benchmark for service requests to help comprehensively evaluate the performance of our systems. The results show that considering service composition and service routing jointly results in connections that have lower end-to-end delay while still meeting all service requirements.

Virtualization is the base for a diversified next-generation network architecture design. Much work has been done on virtualization infrastructure, but it is still unclear how to easily instantiate a network slice that meets a high-level description of network functionality. Our work addresses this problem that occurs at the interface between network service providers and virtualized infrastructure providers. The proposed Service-based Network Virtualization System (SNVS), which is based on our previously developed network service architecture, provides a comprehensive and extensible interface to ease the development of new network services, protocols, and applications in virtualized networks.

Novel network architectures with distributed service components on both routers and end-systems have been proposed to provide the necessary flexibility in the next-generation Internet. Such architectures allow services to be composed along the data path to satisfy different communication requirements. A major operational challenge in such systems is to determine where to perform the required services along the data path. This problem, which we call as the "service placement problem" is proven to be NP-complete when considering resource (e.g., link and processing capacity) constraints. In this paper, we present an evaluation of several existing and newly developed heuristic algorithms for solving the problem. We explore the quality of the achieved placement in terms of effective use of system resources, end-to-end delay, connection drop rate, and load balancing. Our results show the design trade-offs of these different algorithms.

In the next-generation Internet architecture, more functionality will be placed in the data path of routers in the form of "services" and other packet processing features. This trend will increase the amount of state information that is maintained by system inside the network. In this paper, we present a framework for structuring and managing network state information distributed across the next-generation Internet architecture.

Many next-generation Internet architectures propose advanced packet processing functions in the data path of the network. Such "services" are typically performed on some nodes along the path of a packet. We present a novel decentralized algorithm that can determine an allocation of services to network nodes. The algorithm can obtain globally optimal solutions for a single service and approximate solutions for two or more services. In our simulation results, we validate the correctness of the algorithm, quantify the quality of the approximations, and compare the results to those of a centralized algorithm. Our results show that the proposed algorithm presents an effective solution to the service placement problem that can be implemented in a realistic network.

Advanced packet processing functions in the data path of routers are commonly used in the current Internet and are likely to expand in next-generation networks. One of the key challenges related to such “network services” is to develop a suitable control plane infrastructure for routing and connection setup. In this paper, we present a novel distributed algorithm and routing protocol to facilitate allocation of services during connection setup. The protocol is scalable for deployment in large networks and can obtain globally optimal solutions for a single service and approximate solutions for two or more services. We have implemented a prototype on Emulab to evaluate the proposed protocol. Our implementation shows that the proposed protocol is indeed an effective and scalable solution to the routing problem in networks with data-path services.

Modern network processor systems require the ability to adapt their processing capabilities at runtime to changes in network traffic. Traditionally, network processor applications have been optimized for a single static workload scenario, but recently several approaches for runtime adaptation have been proposed. Comparing these approaches and developing novel runtime support algorithms is difficult due to the multicore system-on-a-chip nature of network processors. In this paper, we present a model for network processors that can aid in evaluating different runtime support systems. The model considers workload characteristics of applications and network traffic using a queuing network abstraction. The accuracy of this analytical approach to modeling runtime systems is validated through simulation. We illustrate the effectiveness of our model by comparing the performance of two existing workload adaptation algorithms.

In the next generation Internet architecture, more functionality in the form of "services" and packet processing features will be placed inside the network rather than on end-systems. This trend will increase the amount of network state information maintained by the systems inside the network. We present a framework for structuring and managing network state information that can be used in the next generation Internet architecture.

Modern network processor systems require the ability to adapt their processing capabilities at runtime to changes in network traffic. Traditionally, network processor applications have been optimized for a single static workload scenario, but recently several approaches for run-time adaptation have been proposed. Comparing these approaches and developing novel run-time support algorithms is difficult due to the multicore system-on-a-chip nature of network processors. In this paper, we present a model for network processors that can aid in evaluating different run-time support systems. The model considers workload characteristics of applications and network traffic. We use a queuing network abstraction to model different runtime systems. We illustrate the effectiveness of this model by comparing the performance of two existing workload adaptation algorithms.

The growing convergence among mobile computing devices and smart sensors boosts the development of ubiquitous computing and smart spaces, where localization is an essential part for realizing the big vision. Due to their large size, high cost, and high power consumption, the current widely accepted outdoor localization methods based on GPS and cellular techniques are not suitable for tracking numerous small size and limited power objects. In this paper, we present Scout, an easy-setup and cost- effective outdoor localization system based on off-the- shelf active RFID systems and a probabilistic localization algorithm, which is compatible with the future smart spaces and ubiquitous computing systems. The proposed algorithm is robust to measurement uncertainty and self-adjustive to varying outdoor environments. Using MATLAB simulations, we investigate the system performance dependence on a number of system and environmental parameters. The simulation results prove that the proposed system is an accurate and cost-effective candidate for outdoor localization.