17614044
Measurement Approaches to Evaluate Performance Optimizations for Wide-Area Wireless Networks
We present measurement approaches to evaluate performance optimizations, employed at different layers of the protocol stack, to enhance application performance over wide-area wireless networks (WWANs). Applications running over WWAN cellular environments (e.g web browsing) are significantly affected by the vagaries of the cellular wireless links. Much of the prior research has focussed on variety of isolated performance optimizations and their measurements over wired and wireless environments. In this paper we introduce experiment-based measurement approaches to benchmark application performance using optimizations performed at individual layers of the protocol stack.
11368060
Packet classifiers in ternary CAMs can be smaller
Serving as the core component in many packet forwarding, differentiating and filtering schemes, packet classification continues to grow its importance in today's IP networks. Currently, most vendors use Ternary CAMs (TCAMs) for packet classification. TCAMs usually use brute-force parallel hardware to simultaneously check for all rules. One of the fundamental problems of TCAMs is that TCAMs suffer from range specifications because rules with range specifications need to be translated into multiple TCAM entries. Hence, the cost of packet classification will increase substantially as the number of TCAM entries grows. As a result, network operators hesitate to configure packet classifiers using range specifications. In this paper, we optimize packet classifier configurations by identifying semantically equivalent rule sets that lead to reduced number of TCAM entries when represented in hardware. In particular, we develop a number of effective techniques, which include: trimming rules, expanding rules, merging rules, and adding rules. Compared with previously proposed techniques which typically require modifications to the packet processor hardware, our scheme does not require any hardware modification, which is highly preferred by ISPs. Moreover, our scheme is complementary to previous techniques in that those techniques can be applied on the rule sets optimized by our scheme. We evaluate the effectiveness and potential of the proposed techniques using extensive experiments based on both real packet classifiers managed by a large tier-1 ISP and synthetic data generated randomly. We observe significant reduction on the number of TCAM entries that are needed to represent the optimized packet classifier configurations.
15760
Energy-Efficient Reliable Paths for On-Demand Routing Protocols
We define techniques to compute energy-efficient reliable paths within the framework of on-demand routing protocols. The choice of energy-efficient reliable paths depend on link error rates on different wireless links, which in turn depend on channel noise. We show how our scheme accounts for such channel characteristics in computing such paths. Additionally, we perform a detailed study of the AODV protocol and our energy-efficient variants, under various noise and node mobility conditions. Our results show that our proposed variants of on-demand routing protocols can achieve orders of magnitude improvement in energy-efficiency of reliable data paths.
8584874
Throughput Optimization and Fair Bandwidth Allocation in Multi-Hop Wireless LANs
There is an inherent well-known conflict between fairness and throughput that arises in many networking scenarios. A number of researchers have studied this problem in the context of (single-hop) wireless local area networks (WLANs), where clients directly exchange traffic with access points (APs). More recently, researchers have proposed multi-hop extensions to WLANs where client traffic is forwarded via a series of client-client links. In this paper, we show that the objective of improving throughput without sacrificing fairness can be much better met in multi-hop WLANs. We decouple this objective into two separate but related problems. First, we need an algorithm to organize clients into a multi-hop structure such that fair bandwidth allocation within this structure leads to improved throughput. Second, we need algorithms for performing fair bandwidth allocation within the determined multi-hop structure. In this paper, we first design optimal fair bandwidth allocation algorithms for both max-min throughput fairness and max-min time fairness in multi-hop WLANs. Subsequently, we design an efficient algorithm to find desirable multi-hop structures. With slight modifications, our results in this paper can be generalized to other multi-hop wireless networks as well. Our proposed solutions seamlessly integrate with legacy devices and hence are incrementally deployable. Simulation results demonstrate that our solutions can effectively improve throughput (by up to 114% or more) as well as network coverage while preserving fairness.
3056111
An Analysis of Wireless Network Coding for Unicast Sessions: The Case for Coding-Aware Routing
A recent approach, COPE, for improving the throughput of unicast traffic in wireless multi-hop networks exploits the broadcast nature of the wireless medium through opportunistic network coding. In this paper, we analyze throughput improvements obtained by COPE-type network coding in wireless networks from a theoretical perspective. We make two key contributions. First, we obtain a theoretical formulation for computing the throughput of network coding on any wireless network topology and any pattern of concurrent unicast traffic sessions. Second, we advocate that routing be made aware of network coding opportunities rather than, as in COPE, being oblivious to it. More importantly, our work studies the tradeoff between routing flows "close to each other" for utilizing coding opportunities and "away from each other" for avoiding wireless interference. Our theoretical formulation provides a method for computing source-destination routes and utilizing the best coding opportunities from available ones so as to maximize the throughput. We handle scheduling of broadcast transmissions subject to wireless transmit/receive diversity and link interference in our optimization framework. Using our formulations, we compare the performance of traditional unicast routing and network coding with coding-oblivious and coding-aware routing on a variety of mesh network topologies, including some derived from contemporary mesh network testbeds. Our evaluations show that a route selection strategy that is aware of network coding opportunities leads to higher end-to-end throughput when compared to coding-oblivious routing strategies.
14357613
Construction of an efficient overlay multicast infrastructure for real-time applications
This paper presents an overlay architecture where service providers deploy a set of service nodes (called MSNs) in the network to efficiently implement media-streaming applications. These MSNs are organized into an overlay and act as application-layer multicast forwarding entities for a set of clients. We present a decentralized scheme that organizes the MSNs into an appropriate overlay structure that is particularly beneficial for real-time applications. We formulate our optimization criterion as a "degree-constrained minimum average-latency problem" which is known to be NP-hard. A key feature of this formulation is that it gives a dynamic priority to different MSNs based on the size of its service set. Our proposed approach iteratively modifies the overlay tree using localized transformations to adapt with changing distribution of MSNs, clients, as well as network conditions. We show that a centralized greedy approach to this problem does not perform quite as well, while our distributed iterative scheme efficiently converges to near-optimal solutions.
13275687
Exploiting program execution phases to trade power and performance for media workload
Processing streaming media comprises several program phases (often distinct) that are periodic and independent of application data. In this paper we characterize execution of such programs into execution phases based on their dynamic IPC (Instruction Per Cycle) profile. We show that program execution of selected phases can be dynamically boosted by activating additional standby functional units which ae otherwise powered down for saving energy. Through simulation we show that speedup ranging from 1.1 to 1.25 can be achieved while reducing the energy-delay product (EDP) for most of the media benchmarks evaluated. Additionally we show that artificially introduced stalls during phases of processor underutilization reduces power by around 2 to 4%.
16229600
Packet dropping policies for ATM and IP networks
Selective packet dropping policies have been used to reduce congestion and transmission of traffic that would inevitably be retransmitted. For data applications using best-effort services, packet dropping policies (PDPs) are congestion management mechanisms implemented at each intermediate node that decide, reactively or proactively, to drop packets to reduce congestion and free up precious buffer space. While the primary goal of PDPs is to avoid or combat congestion, the individual PDP designs can significantly affect application throughput, network utilization, performance fairness, and synchronization problems with multiple transmission control protocol (TCP) connections. Scalability and simplicity are also important design issues. This article surveys the most important selective packet dropping policies that have been designed for best-effort traffic in ATM and IP networks, providing a comprehensive comparison between the different mechanisms.
30399081
Hypercube connected rings: a fault-tolerant and scalable architecture for virtual lightwave network topology
A new, fault-tolerant, scalable, and modular virtual topology for lightwave networks employing wavelength division multiplexing is proposed. The proposed architecture is based on a hypercube connected ring structure that enjoys the rich topological properties of a hypercube, but it also overcomes one of its drawbacks. In a hypercube, the nodal degree increases with the number of nodes. Hence, the per-node cost of the network increase as the network size grows. However, in a hypercube connected ring network (HCRNet) the nodal degree is small and it remains constant, independent of the network population. The HCRNet, like the hypercube, is perfectly symmetric in the sense that average internodal distance in an N-node HCRNet is the same from any source node. Its average internodal distance is in the order of logN and it is comparable to other regular structures such as Trous and ShuffleNet. The authors present the structural properties of the HCRNet and the network routing.<<ETX>>
9170580
Network latency optimizations in distributed database systems
The advent of high-speed networks will enable the deployment of data-server systems (currently used in LANs) over WANs. The users of these systems will have the same high expectations with respect to performance parameters (such as the transaction throughput, response time and system reliability) as in the case of LANs. Thus, it is important to study the performance of existing distributed database protocols in the new networking environment, identify the performance bottlenecks and develop protocols that are capable of taking advantage of the high-speed networking technology. As a first step, in this paper, we examine the scalability of the server-based two-phase locking (s-2PL) protocol, and discuss three optimizations which allow the s-2PL protocol to be tailored for high-speed WAN environments where the size of the message is less of a concern than the number of rounds of message passing. These optimizations, collectively called the group two-phase locking (g-2PL) protocol, reduce the number of rounds of message passing by grouping lock grants, client-end caching and data migration. In a simulation study, 20-25% improvement in the response time of the g-2PL protocol over that of the s-2PL protocol was observed.
14976055
A new token passing distributed mutual exclusion algorithm
Eliminating interference between concurrently executing activities through mutual exclusion is one of the most fundamental problems in computer systems. The problem of mutual exclusion in a distributed system is especially interesting owing to the lack of global knowledge in the presence of variable communication delays. In this paper, a new token-based distributed mutual exclusion algorithm is proposed. The algorithm incurs approximately three messages at high loads, irrespective of the number of nodes N in the system. At low loads, it requires approximately N messages. The paper also addresses failure recovery issues, such as token loss.