2626768
MAR: a commuter router infrastructure for the mobile Internet
We introduce MAR, a commuter mobile access router infrastructure that exploits wireless diversity (e.g. channel diversity, network diversity, and technology diversity) to provide improved data performance for wireless data users. Our system design stems from the observation that rather than choosing a single wireless service provider (e.g. Sprint, AT&T, BT, Vodafone), a single technology (e.g. GPRS, UMTS, CDMA, 802.11), or a single wireless channel, users can obtain significant benefits by using the multiplicity of choices available. MAR is a wireless multi-homed device that can be placed in moving vehicles (e.g. car, bus, train) to enable high-speed data access. MAR dynamically instantiates new channels based on traffic demand, aggregates the bandwidth and dynamically shifts load from poor quality to better quality channels. MAR, thus, provides a faster, more stable, and reliable communication channel to mobile users.We have implemented and tested the MAR system in our testbed which spans the networks of three different cellular providers. Through our experiments we have performed a detailed evaluation to quantify the benefits of MAR for different protocols and applications. For example, even in highly mobile environments, MAR, on average, improves the end-user experience of web-browsing and streaming applications by a factor of 2.8 and 4.4 respectively. Our results show that significant benefits can be obtained by exploiting the diversity in coverage offered by many cellular operators, different technology networks (e.g. GPRS, CDMA), and diverse wireless channels.
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.
41447667
Load Balancing in Large-Scale RFID Systems
A radio frequency identifier (RFID) system consists of inexpensive, uniquely-identifiable tags that are mounted on physical objects, and readers that track these tags (and hence these physical objects) through RF communication. In this paper we, therefore, address this load balancing problem for readers - given a set of tags that are within range of each reader, which of these tags should each reader be responsible for such that the cost for monitoring tags across the different readers is balanced, while guaranteeing that each tag is monitored by at least one reader. We show that a generalized variant of the load balancing problem is NP-hard and hence present a 2-approximation centralized algorithm. We next present an optimal centralized solution for a specialized variant. Subsequently, we present a localized distributed algorithm that is probabilistic in nature and closely matches the performance of the centralized algorithms. Our results demonstrate that our schemes achieve very good performance even in highly dynamic large-scale RFID systems.
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.
7316736
Efficient probabilistic packet marking
Probabilistic packet marking is a general technique which routers can use to reveal internal network information to end-hosts. Such information is probabilistically set by the routers in headers of regular IP packets on their way to destinations. A number of potential applications have been identified, such as IP traceback, congestion control, robust routing algorithms, dynamic network reconfiguration, and locating Internet bottlenecks, etc. In this paper, we define EPPM, an efficient general probabilistic packet marking scheme with a wide range of potential applications, of which locating Internet bottlenecks and IP traceback are investigated as two representative examples to demonstrate its effectiveness. Our proposed scheme imposes only a single-bit overhead in the IP packet headers. More importantly, it significantly reduces the number of IP packets required to convey the relevant information when compared to the prior best known scheme (almost by two orders of magnitude)
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.
17891154
A Credit-Based Active Queue Management (AQM) Mechanism to Achieve Fairness in the Internet
Router-based algorithms to address the TCP-friendliness problem have focused on providing fairness to TCP connections by penalizing UDP unresponsive flows. As a result, current schemes have overlooked their effect on streaming applications. In addition, current schemes have not been widely implemented in practice because of their high complexity and their inability to provide fairness when multiple unresponsive flows, packets of different sizes, and bursty traffic are present. All these aspects and scenarios, commonly found in practice, are rarely addressed in the literature. In this paper, we present Achieving Fairness using a Credit-based mechanism or AFC, a simple Fair Active Queue Management (FAQM) mechanism that aims to solve the unfairness problems generated under these realistic conditions. Simulation results show that AFC provides smoother transfer rates for unresponsive flows transmitting real-time traffic, handles multiple heavy unresponsive flows better, improves the fairness among TCP connections with different round-trip delays, and achieves good fairness even under bursty traffic and packets of different sizes.
13955721
Improving bandwidth utilization based on deterministic delay bound in connection-oriented networks
Packet scheduling disciplines play an important role in providing quality of service (QoS) guarantees to applications traffic in high speed networks. Several scheduling disciplines have emerged in the literature that are capable of providing guarantees on various QoS parameters, such as packet delay, jitter, loss and throughput, while maintaining fairness among various connections. However, there is a trade-off between the performance and the simplicity of operation and implementation performance of the scheduling schemes. Thus the first-come-first-serve (FCFS) scheduling discipline has remained popular due to its overriding simplicity in spite of its poor capabilities in providing QoS guarantees. In previous work it has been shown that a practical worst case bound can be obtained for a deterministic delay guarantee in networks using the FCFS discipline, by imposing a source rate condition on each connection, that restricts the overall network utilization. In this paper, a modified source rate condition is proposed that can significantly increase the bandwidth utilization, while still maintaining the deterministic delay guarantee.
22414487
On the Effectiveness of Flow Aggregation in Improving Instruction Reuse in Network Processing Applications
Instruction Reuse is a microarchitectural technique that exploits dynamic instruction repetition to remove redundant computations at run-time. In this paper we examine instruction reuse of integer ALU and load instructions in network processing applications and attempt to answer the following questions: (1) How much of instruction repetition can be reused in packet processing applications?, (2) Can the temporal locality of network traffic be exploited to reduce interference in the Reuse Buffer and improve reuse? and (3) What is the effect of reuse on microarchitectural features such as resource contention and memory accesses? We use an execution driven simulation methodology to evaluate instruction reuse and find that for the benchmarks considered, 1 to 50% of the dynamic instructions are reused yielding performance improvement between 1 and 20%. To further improve reuse, a flow aggregation scheme as well as an architecture for exploiting the same is proposed. This scheme is mostly applicable to header processing applications and exploits temporal locality in packet data to uncover higher reuse. As a side effect, instruction reuse reduces memory traffic and improves performance.
20080343
A survey of adaptive bandwidth control algorithms
In packet-switched network traffic management and control, efficiently allocating bandwidth to provide quantitative packet-level QoS to aggregate traffic has been difficult due to unpredictable, unknown statistical characteristics of the aggregate traffic. With inaccurate traffic information, using static bandwidth allocation results in the network being underutilized, or the QoS requirement not being satisfied. An alternative is to use adaptive bandwidth control (ABC), whereby the allocated bandwidth is regularly adjusted over the packet-level time scale to attain a given QoS requirement. This paper provides a literature review of ABC algorithms that guarantee aggregate traffic packet-level QoS metrics, such as the average queue length, packet loss, and packet delay. We describe different ABC algorithms, identify their advantages and shortcomings, and provide some comparative performance evaluation results. Open issues in ABC for future research directions are also discussed.
52854658
Adaptive bandwidth control for efficient aggregate QoS provisioning
Internet links operate at high speeds, and past trends predict that these speeds will continue to increase rapidly. Routers and Intrusion Detection Systems that operate at up to OC-768 speeds (40 Gigabits/second) are currently being developed. In this paper we address a basic function common to several security and measurement applications running at line speeds: counting the number of distinct header patterns (flows) seen on a high speed link in a specified time period. For example one can detect port scans by counting the number of connections opened by the suspected port scanner and one can ascertain that a denial of service attack is in progress by counting the number of distinct (fake) source addresses that send packets to the suspected victim. We provide algorithms solving the flow counting problem using extremely small amounts of memory. This can translate into savings of scarce fast memory (SRAM) for hardware implementations. It can also help systems that use cheaper DRAM to allow them to scale to larger instances of the problem. The reduction in memory is particularly important for network security applications such as detecting port scans and DoS attacks that need to run a separate instance of the algorithm for each suspected attacker or victim. Our algorithms can be implemented in hardware at wire speeds (8 nsec per packet for OC-768) using simple CRC based hash functions, multiplexers and SRAM. They access at most one or two memory locations per packet. We expose the behavior of simple building blocks and provide a family of customizable counting algorithms that can be adapted to the requirements of various applications. This allows our algorithms to use less memory than the best known counting algorithm, probabilistic counting, to provide the same accuracy. • Virtual bitmap is well suited for triggers (which need only be accurate around a threshold value) such as detecting DoS attacks, and uses 292 bytes to achieve an error of 2.619% compared to 5,200 bytes for probabilistic counting. • Our “no assumptions” counting algorithm, multiresolution bitmap algorithms uses only 2143 bytes to count up to 100 million flows with an average error of 3%. Its accuracy is slightly better when the number of flows is small, while the accuracy of probabilistic counting using the same memory is much worse. • Our adaptive bitmap that exploits stationarity in the number of flows can count the number of distinct flows on a link that contains anywhere from 0 to 100 million flows with an average error of less than 1 % using only 2 Kbytes of memory. Probabilistic counting needs eight times more memory to achieve the same accuracy. • We used our triggered bitmap to replace the port scan detection component of the popular intrusion detection system Snort. Doing so reduced the memory usage from 89 Mbytes to 6.4 Mbytes (with an average error of 13.5%) as measured on a 10 minute trace. Probabilistic counting uses 23 Mbytes. This work was made possible by a grant from NIST for the Sensilla Project. King: Estimating Latency between Arbitrary Internet End Hosts ∗ Krishna P. Gummadi, Stefan Saroiu, Steven D. Gribble Department of Computer Science & Engineering University of Washington Seattle, WA, USA, 98195-2350 {tzoompy,gummadi,gribble}@cs.washington.edu The ability to estimate network latencies accurately between arbitrary Internet end hosts would enable wide-area measurement studies and applications, such as investigating routing path inefficiencies on a wide-scale [1] or constructing topologically sensitive overlay networks. In this poster we present King [2], a tool that accurately, quickly and cheaply estimates the latency between arbitrary end hosts by using existing DNS infrastructure in a novel way. Our approach is inspired by tools like Sting [3] and TBIT [4], which show that it is possible to use existing protocols in unanticipated ways to obtain results that were previously intractable. Our technique relies on two observations. First, given a pair of end hosts to be measured, in most cases it is possible for King to find their authoritative DNS name servers that are topologically close to the end hosts. Second, given a pair of DNS name servers, King can accurately estimate the latency between them using recursive DNS queries. Thus, King is able to use the measured latency between the name servers as an estimate of the latency between the end hosts. Although this estimate will inevitably suffer from inaccuracies, our extensive evaluation demonstrates that this estimation error is small (less than 20% error in over three-quarters of generated estimates). Compared to previous approaches like IDMaps [5] and GNP [6], King has two primary advantages (1) deployability and (2) accuracy. 1. Deployability: Unlike IDMaps, King does not require the deployment of additional infrastructure, and unlike GNP, King does not require end hosts to agree upon a single set of landmarks or share the coordinates with other end hosts. Because King uses existing DNS infrastructure, it scales naturally in terms of the number hosts that could be measured. Our evaluation indicates that King can be used to estimate latencies between arbitrary IP hosts more than 75% of time in the Internet today. 2. Accuracy: Unlike IDMaps and GNP the accuracy of King is not affected by the placement of measurement points (tracers or landmarks) in the Internet. King’s estimates are based on direct online measurements rather than extrapolation from latencies This work was supported by National Science Foundation under ITR grant No. CCR-0121341. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation. of a subset of paths measured offline. Our evaluation shows that the error in King latency estimates between end hosts is significantly smaller than that of IDMaps, while the error in its estimates between name servers is negligible. Further, we show that King can identify those of its own estimates that are likely to be inaccurate. These characteristics make King an ideal tool for a number of wide-area measurement studies that involve measuring latencies accurately between a large number of geographically distant end hosts. King is also fast and lightweight requiring the generation of only a few packets to produce an estimate. Our evaluation also demonstrates that (a) King preserves order among its latency estimates; a feature useful in identifying a close server from a group of server replicas and (b) authoritative name servers are located topologically close to their end hosts in a majority of scenarios (i.e., latencies as measured from a far away host to both the end host and its name server are very similar); this explains the high accuracy of King. Finally, we test the feasibility of using King for measurement studies by performing Detour study [1] on a larger scale. The results we obtained are consistent with the earlier Detour study. We were able to obtain our results with far greater ease as, unlike the previous study, we were not restricted to the publicly available traceroute servers and their usage policies. We also believe that the simplicity of our King tool will enable researchers to use it in myriads of unanticipated ways like the more popular Ping tool.