In this article, we consider a perimeter defense problem in a planar conical environment in which$M$identical vehicles, each having a finite capture radius, seek to defend a concentric perimeter from mobile intruders. The intruders are released at the circumference of the environment at arbitrary times and in any number. Upon release, each intruder moves radially toward the perimeter with fixed speed. We provide a worst-case analysis of this problem. Specifically, we present acompetitive analysisapproach to this problem by measuring the performance of decentralized and cooperative online algorithms for the vehicles against arbitrary inputs, relative to an optimal offline algorithm that has information about entire intruder release sequence in advance. We first establish a necessary condition on the problem parameters that guarantees finite competitiveness ofanyalgorithm. We then design and analyze three decentralized and two cooperative online algorithms and characterize parameter regimes in which they have finite competitive ratios. Specifically, our first two decentralized algorithms are provably 1 and 2-competitive, respectively, whereas our third decentralized algorithm exhibits different competitive ratios in different regimes of problem parameters. Our first cooperative algorithm is 1.5-competitive and our second cooperative algorithm exhibits different competitive ratios in different regimes of problem parameters. Finally, we provide multiple numerical plots in the parameter space to reveal additional insights into the relative performance of our algorithms and discuss an extension to the case of heterogeneous vehicles.

Monitoring distributed systems to ensure their correctness is a challenging and expensive but essential problem. It is challenging because while execution of a distributed system creates a partial order among events, the monitor will typically observe only one serialization of that partial order. This means that even if the observed serialization is consistent with the system specifications, the monitor cannot assume that the system is correct because some other unobserved serialization can be inconsistent with the system specifications. Existing solutions that guarantee identification of all such unobserved violations require some combination of lots of time and large clocks, e.g. O(n) sized Vector Clocks.We present a new, efficient two-layered monitoring approach that overcomes both the time and space limitations of earlier monitors. The first layer is imprecise but efficient and the second layer is precise but (relatively) inefficient. We show that the combination of these two layers reduces the cost of monitoring by 85-95%. Furthermore, the two-layered monitor permits the use of O(1) sized Hybrid Logical Clocks.

Packet classification is an important part of many networking devices, such as routers and firewalls. Software-defined networking (SDN) heavily relies on online packet classification which must efficiently process two different streams: incoming packets to classify and rules to update. This rules out many offline packet classification algorithms that do not support fast updates. We propose a novel online classification algorithm, TupleMerge (TM), derived from tuple space search (TSS), the packet classifier used by Open vSwitch (OVS). TM improves upon TSS by combining hash tables which contain rules with similar characteristics. This greatly reduces classification time preserving similar performance in updates. We validate the effectiveness of TM using both simulation and deployment in a full-fledged software router, specifically within the vector packet processor (VPP). In our simulation results, which focus solely on the efficiency of the classification algorithm, we demonstrate that TM outperforms all other state of the art methods, including TSS, PartitionSort (PS), and SAX-PAC. For example, TM is 34% faster at classifying packets and 30% faster at updating rules than PS. We then experimentally evaluate TM deployed within the VPP framework comparing TM against linear search and TSS, and also against TSS within the OVS framework. This validation of deployed implementations is important as SDN frameworks have several optimizations such as caches that may minimize the influence of a classification algorithm. Our experimental results clearly validate the effectiveness of TM. VPP TM classifies packets nearly two orders of magnitude faster than VPP TSS and at least one order of magnitude faster than OVS TSS.

Many networking devices, such as firewalls and routing tables, rely upon packet classifiers to define their behavior for various kinds of network traffic. Since these devices have real-time constraints, it is important for packet classification to be as fast as possible. We present a new method, ByteCuts, which includes two major improvements over existing tree-based packet classifiers. First, it introduces a new cutting method that is more efficient than existing methods. Second, ByteCuts intelligently partitions the rule list into multiple trees in a way that supports the cutting method and reduces rule replication. We compare ByteCuts to several existing methods such as HyperCuts, HyperSplit, and SmartSplit. We find that ByteCuts outperforms SmartSplit, the previous fastest classifier, in every metric; specifically, ByteCuts is able to classify packets 58% faster, can be constructed in seconds rather than minutes, and uses orders of magnitude less memory.

Packet classification is an important part of many networking devices, such as routers and firewalls. Software-defined networks require online packet classification where classifiers receive a mixed stream of packets to classify and rules to update and both operations must be completed as efficiently as possible without knowledge of future operations. This rules out many classifiers, such as HyperCuts, HyperSplit, and their derivatives, which do not support fast updates. We build upon Tuple Space Search, the packet classifier used by Open vSwitch, to create TupleMerge. TupleMerge improves upon Tuple Space Search by combining hash tables which contain rules with similar characteristics. This greatly reduces classification time by producing fewer tables. We compared TupleMerge to PartitionSort, the current state-of-the-art online packet classifier, on rulelists generated by ClassBench. TupleMerge outperforms PartitionSort at both classifying packets and rule update. Specifically, on average, it is 34.2% faster at classifying packets and 30% faster at updating rules than PS.

OpenFlow packet classification needs to satisfy two requirements: high speed and fast updates. Although packet classification is a well-studied problem, no existing solution satisfies both requirements. Decision tree methods, such as HyperCuts, EffiCuts, and SmartSplit can achieve high-speed packet classification but not fast updates. The Tuple Space Search (TSS) algorithm used in Open vSwitch achieves fast updates but not high-speed packet classification. In this paper, we propose a hybrid approach, PartitionSort, that combines the benefits of both TSS and decision trees achieving both high-speed packet classification and fast updates. A key to PartitionSort is a novel notion of ruleset sortability that provides two key benefits. First, it results in far fewer partitions than TSS. Second, it allows the use of Multi-dimensional Interval Trees to achieve logarithmic classification and update time for each sortable ruleset partition. Our extensive experimental results show that PartitionSort is an order of magnitude faster than TSS in classifying packets while achieving comparable update time. PartitionSort is a few orders of magnitude faster in construction time than SmartSplit, a state-of-the-art decision tree classifier, while maintaining competitive classification time. Finally, PartitionSort is scalable to an arbitrary number of fields.

Access control lists (ACLs) are the core of many networking and security devices. As new threats and vulnerabilities emerge, ACLs on routers and firewalls are getting larger. Therefore, compressing ACLs is an important problem. In this paper, we propose a new approach, called Diplomat, to ACL compression. The key idea is to transform higher dimensional target patterns into lower dimensional patterns by dividing the original pattern into a series of hyperplanes and then resolving differences between two adjacent hyperplanes by adding rules that specify the differences. This approach is fundamentally different from prior ACL compression algorithms and is shown to be very effective. We implemented Diplomat and conducted side-by-side comparison with the prior Firewall Compressor, TCAM Razor, and ACL Compressor algorithms on real life classifiers. Our experimental results show that Diplomat outperforms all of them on most of our real-life classifiers, often by a considerable margin, particularly as classifier size and complexity increases. In particular, on our largest ACLs, Diplomat has an average improvement ratio of 34.9% over Firewall Compressor on range-ACLs, of 14.1% over TCAM Razor on prefix-ACLs, and 8.9% over ACL Compressor on mixed-ACLs.

Packet classification is the core mechanism that enables many networking devices. Although using ternary content addressable memory (TCAM) to perform high-speed packet classification has become the widely adopted solution, TCAM is very expensive, has limited capacity, consumes large amounts of power, and generates tremendous amounts of heat because of their extremely dense and parallel circuitry. In this paper, we propose the first packet classification scheme that uses binary CAM (BCAM). BCAM is similar to TCAM except that in BCAM, every bit has only two possible states: 0 or 1; in contrast, in TCAM, every bit has three possible states: 0, 1, or * (don't care). Because of the high complexity in implementing the extra “don't care” state, TCAM has much higher circuit density than BCAM. As the power consumption, heat generation, and price grow non-linearly with circuit density, BCAM consumes much less power, generates much less heat, and costs much less money than TCAM. Our BCAM-based packet classification scheme is built on two key ideas. First, we break a multi-dimensional lookup into a series of 1-D lookups. Second, for each 1-D lookup, we convert the ternary matching problem into a binary string exact matching problem. To speed up the lookup process, we propose a number of optimization techniques, including skip lists, free expansion, minimizing maximum lookup time, minimizing average lookup time, and lookup short circuiting. We evaluated our BCAM scheme on 17 real-life packet classifiers. On these classifiers, our BCAM scheme requires roughly five times fewer CAM bits than the traditional TCAM-based scheme. The penalty is a throughput that is roughly four times less.

Regular expression (RegEx) matching, the core operation of intrusion detection and prevention systems, remains a fundamentally challenging problem. A desired RegEx matching scheme should satisfy four requirements: deterministic finite state automata (DFA) speed, nondeterministic finite state automata (NFA) size, automated construction, and scalable construction. Despite lots of work on RegEx matching, no prior scheme satisfies all four of these requirements. In this paper, we approach this holy grail by proposing OverlayCAM, a RegEx matching scheme that satisfies all four requirements. The theoretical underpinning of our scheme is overlay delayed input DFA, a new automata model proposed in this paper that captures both state replication and transition replication, which are inherent in DFAs. Our RegEx matching solution processes one input character per lookup like a DFA, requires only the space of an NFA, is grounded in sound automata models, is easy to deploy in existing network devices, and comes with scalable and automated construction algorithms.

In this paper, we consider a variety of scheduling problems where n jobs with release times are to be scheduled non-preemptively on a set of m identical machines. The problems considered are machine minimization, (weighted) throughput maximization and min-sum objectives such as (weighted) flow time and (weighted) tardiness. We develop a novel quasi-polynomial time dynamic programming framework that gives O(l)-speed O(l)-approximation algorithms for the offline versions of machine minimization and min-sum problems. For the weighted throughput problem, the framework gives a (1 + ε)-speed (1 – ε)-approximation algorithm. The generic DP is based on improving a naïve exponential time DP by developing a sketching scheme that compactly and accurately approximates parameters used in the DP states. We show that the loss of information due to the sketching scheme can be offset with limited resource augmentation. This framework is powerful and flexible, allowing us to apply it to this wide range of scheduling objectives and settings. We also provide new insight into the relative power of speed augmentation versus machine augmentation for non-preemptive scheduling problems; specifically, we give new evidence for the power and importance of extra speed for some non-preemptive scheduling problems. This novel DP framework leads to many new algorithms with improved results that solve many open problems, albeit with quasi-polynomial running times. We highlight our results as follows. For the problems with min-sum objectives, we give the first O(l)-speed O(l)-approximation algorithms for the multiple-machine setting. Even for the single machine case, we reduce both the resource augmentation required and the approximation ratios. In particular, our approximation ratios are either 1 or 1 + ε. Most of our algorithms use speed 1 + e or 2 + ε. We also resolve an open question (albeit with a quasi-polynomial time algorithm) of whether less than 2-speed could be used to achieve an O(1)-approximation for flow time. New techniques are needed to address this open question since it was proven that previous techniques are insufficient. We answer this open question by giving an algorithm that achieves a (1 + ε)-speed 1-approximation for flow time and (1 + ε)-speed (1 + ε)-approximation for weighted flow time. For the machine minimization problem, we give the first result using constant resource augmentation by showing a (1 + ε)-speed 2-approximation, and the first result only using speed augmentation and no additional machines by showing a (2 + ε)-speed 1-approximation. We complement our positive results for machine minimization by considering the discrete variant of the problem and show that no algorithm can use speed augmentation less than 2log1–εand achieve approximation less than O(log log n) for any constant ε > 0 unless NP admits quasi-polynomial time optimal algorithms. Thus, our results show a stark contrast between the two settings. In one, constant speed augmentation is sufficient whereas in the other, speed augmentation is essentially not effective.

One of the key challenges facing wireless sensor networks (WSNs) is extending network lifetime due to sensor nodes having limited power supplies. Extending WSN lifetime is complicated because nodes often experience differential power consumption. For example, nodes closer to the sink in a given routing topology transmit more data and thus consume power more rapidly than nodes farther from the sink. Inspired by the huddling behavior of emperor penguins where the penguins take turns on the cold extremities of a penguin “huddle”, we propose mobile node rotation, a new method for using low-cost mobile sensor nodes to address differential power consumption and extend WSN lifetime. Specifically, we propose to rotate the nodes through the high power consumption locations. We propose efficient algorithms for single and multiple rounds of rotations. Our extensive simulations show that mobile node rotation can extend WSN topology lifetime by more than eight times on average which is significantly better than existing alternatives.

Packet classification is the core mechanism that enables many networking devices. Although using Ternary Content Addressable Memories (TCAMs) to perform high speed packet classification has become the widely adopted solution, TCAMs are very expensive, have limited capacity, consume large amounts of power, and generate tremendous amounts of heat because of their extremely dense and parallel circuitry. In this paper, we propose the first packet classification scheme that uses Binary Content Addressable Memories (BCAMs). BCAMs are similar to TCAMs except that in BCAMs, every bit has only two possible states: 0 or 1; in contrast, in TCAMs, every bit has three possible states: 0, 1, or * (don't care). Because of the high complexity in implementing the extra “don't care” state, TCAMs have much higher circuit density than BCAMs. As the power consumption, heat generation, and price grow non-linearly with circuit density, BCAMs consume much less power, generate much less heat, and cost much less money than TCAMs. Our BCAM based packet classification scheme is built on two key ideas. First, we break a multi-dimensional lookup into a series of one-dimensional lookups. Second, for each one-dimensional lookup, we convert the ternary matching problem into a binary string exact matching problem. To speed up the lookup process, we propose a number of optimization techniques including skip lists, free expansion, minimizing maximum lookup time, minimizing average lookup time, and lookup short circuiting. We evaluated our BCAM scheme on 17 real-life packet classifiers. On these classifiers, our BCAM scheme requires roughly 5 times fewer CAM bits than the traditional TCAM based scheme. The penalty is a throughput that is roughly 4 times less.

Regular expression (RegEx) matching, the core operation of intrusion detection and prevention systems, remains a fundamentally challenging problem. A desired RegEx matching scheme should satisfy four requirements: DFA speed, NFA size, automated construction, and scalable construction. Despite lots of work on RegEx matching, no prior scheme satisfies all four of these requirements. In this paper, we approach this holy grail by proposing OverlayCAM, a RegEx matching scheme that satisfies all four requirements. The theoretical underpinning of our scheme is OD2FA, a new automata model proposed in this paper that captures both state and transition replication inherent in DFAs. Our RegEx matching solution processes one input character per lookup like a DFA, requires only the space of an NFA, is grounded in sound automata models, is easy to deploy in existing network devices, and comes with scalable and automated construction algorithms.

We introduce a scheduling algorithm Intermediate-SRPT, and show that it is O(log P)-competitive with respect to average waiting time when scheduling jobs whose parallelizability is intermediate between being fully parallelizable and sequential. Here the parameter P denotes the ratio between the maximum job size to the minimum. We also show a general matching lower bound on the competitive ratio. Our analysis builds on an interesting combination of potential function and local competitiveness arguments.

In this paper, we propose FlowSifter, a framework for automated online application protocol field extraction. FlowSifter is based on a new grammar model called Counting Regular Grammars (CRG) and a corresponding automata model called Counting Automata (CA). The CRG and CA models add counters with update functions and transition guards to regular grammars and finite state automata. These additions give CRGs and CAs the ability to parse and extract fields from context sensitive application protocols. These additions also facilitate fast and stackless approximate parsing of recursive structures. These new grammar models enable FlowSifter to generate optimized Layer 7 field extractors from simple extraction specifications. We compare FlowSifter against both BinPAC and UltraPAC, which represent the state-of-the-art field extractors. Our experiments show that when compared to BinPAC parsers, FlowSifter runs more than 21 times faster and uses 49 times less memory. When compared to UltraPAC parsers, FlowSifter extractors run 12 times faster and use 24 times less memory.

Regular expression (RE) matching is a core component of deep packet inspection in modern networking and security devices. In this paper, we propose the first hardware-based RE matching approach that uses ternary content addressable memory (TCAM), which is available as off-the-shelf chips and has been widely deployed in modern networking devices for tasks such as packet classification. We propose three novel techniques to reduce TCAM space and improve RE matching speed: transition sharing, table consolidation, and variable striding. We tested our techniques on eight real-world RE sets, and our results show that small TCAMs can be used to store large deterministic finite automata (DFAs) and achieve potentially high RE matching throughput. For space, we can store each of the corresponding eight DFAs with 25 000 states in a 0.59-Mb TCAM chip. Using a different TCAM encoding scheme that facilitates processing multiple characters per transition, we can achieve potential RE matching throughput of 10-19 Gb/s for each of the eight DFAs using only a single 2.36-Mb TCAM chip.

Network intrusion detection and prevention systems commonly use regular expression (RE) signatures to represent individual security threats. While the corresponding deterministic finite state automata (DFA) for any one RE is typically small, the DFA that corresponds to the entire set of REs is usually too large to be constructed or deployed. To address this issue, a variety of alternative automata implementations that compress the size of the final automaton have been proposed such as extended finite automata (XFA) and delayed input DFA (D2FA). The resulting final automata are typically much smaller than the corresponding DFA. However, the previously proposed automata construction algorithms do suffer from some drawbacks. First, most employ a “Union then Minimize” framework where the automata for each RE are first joined before minimization occurs. This leads to an expensive nondeterministic finite automata (NFA) to DFA subset construction on a relatively large NFA. Second, most construct the corresponding large DFA as an intermediate step. In some cases, this DFA is so large that the final automaton cannot be constructed even though the final automaton is small enough to be deployed. In this paper, we propose a “Minimize then Union” framework for constructing compact alternative automata focusing on the D2FA. We show that we can construct an almost optimal final D2FA with small intermediate parsers. The key to our approach is a space- and time-efficient routine for merging two compact D2FA into a compact D2FA. In our experiments, our algorithm runs on average 155 times faster and uses 1500 times less memory than previous algorithms. For example, we are able to construct a D2FA with over 80 000 000 states using only 1 GB of main memory in only 77 min.

Packet classification is the key mechanism for enabling many networking and security services. Ternary Content Addressable Memory (TCAM) has been the industrial standard for implementing high-speed packet classification because of its constant classification time. However, TCAM chips have small capacity, high power consumption, high heat generation, and large area size. This paper focuses on the TCAM-based Classifier Compression problem: given a classifier C, we want to construct the smallest possible list of TCAM entries T that implement C. In this paper, we propose the Ternary Unification Framework (TUF) for this compression problem and three concrete compression algorithms within this framework. The framework allows us to find more optimization opportunities and design new TCAM-based classifier compression algorithms. Our experimental results show that the TUF can speed up the prior algorithm TCAM Razor by twenty times or more and leads to new algorithms that improve compression performance over prior algorithms by an average of 13.7% on our largest real life classifiers.

Access Control Lists (ACLs) are the core of many networking and security devices. As new threats and vulnerabilities emerge, ACLs on routers and firewalls are getting larger. Therefore, compressing ACLs is an important problem. In this paper, we propose a new approach, called Diplomat, to ACL compression. The key idea is to transform higher dimensional target patterns into lower dimensional patterns by dividing the original pattern into a series of hyperplanes and then resolving differences between two adjacent hyperplanes by adding rules that specify the differences. This approach is fundamentally different from prior ACL compression algorithms and is shown to be very effective. We implemented Diplomat and conducted side-by-side comparison with the prior Firewall Compressor algorithm on real life classifiers. The experimental results show that Diplomat outperforms Firewall Compressor most of the time, often by a considerable margin. In particular, on our largest ACLs, Diplomat has an average improvement ratio over Firewall Compressor of 30.6%.

Wireless Sensor Networks (WSNs) are increasingly used in data-intensive applications such as microclimate monitoring, precision agriculture, and audio/video surveillance. A key challenge faced by data-intensive WSNs is to transmit all the data generated within an application's lifetime to the base station despite the fact that sensor nodes have limited power supplies. We propose using low-cost disposable mobile relays to reduce the energy consumption of data-intensive WSNs. Our approach differs from previous work in two main aspects. First, it does not require complex motion planning of mobile nodes, so it can be implemented on a number of low-cost mobile sensor platforms. Second, we integrate the energy consumption due to both mobility and wireless transmissions into a holistic optimization framework. Our framework consists of three main algorithms. The first algorithm computes an optimal routing tree assuming no nodes can move. The second algorithm improves the topology of the routing tree by greedily adding new nodes exploiting mobility of the newly added nodes. The third algorithm improves the routing tree by relocating its nodes without changing its topology. This iterative algorithm converges on the optimal position for each node given the constraint that the routing tree topology does not change. We present efficient distributed implementations for each algorithm that require only limited, localized synchronization. Because we do not necessarily compute an optimal topology, our final routing tree is not necessarily optimal. However, our simulation results show that our algorithms significantly outperform the best existing solutions.

This paper introduces cooperative caching policies for minimizing electronic content provisioning cost in Social Wireless Networks (SWNET). SWNETs are formed by mobile devices, such as data enabled phones, electronic book readers etc., sharing common interests in electronic content, and physically gathering together in public places. Electronic object caching in such SWNETs are shown to be able to reduce the content provisioning cost which depends heavily on the service and pricing dependences among various stakeholders including content providers (CP), network service providers, and End Consumers (EC). Drawing motivation from Amazon's Kindle electronic book delivery business, this paper develops practical network, service, and pricing models which are then used for creating two object caching strategies for minimizing content provisioning costs in networks with homogenous and heterogeneous object demands. The paper constructs analytical and simulation models for analyzing the proposed caching strategies in the presence of selfish users that deviate from network-wide cost-optimal policies. It also reports results from an Android phone-based prototype SWNET, validating the presented analytical and simulation results.

In this paper, we introduce FlowSifter, a systematic framework for online application protocol field extraction. FlowSifter introduces a new grammar model Counting Regular Grammars (CRG) and a corresponding automata model Counting Automata (CA). The CRG and CA models add counters with update functions and transition guards to regular grammars and finite state automata. These additions give CRGs and CAs the ability to parse and extract fields from context sensitive application protocols. These additions also facilitate fast and stackless approximate parsing of recursive structures. These new grammar models enable FlowSifter to generate optimized Layer 7 field extractors from simple extraction specifications. In our experiments, we compare FlowSifter against both BinPAC and UltraPAC, which are the freely available state of the art field extractors. Our experiments show that when compared to UltraPAC parsers, FlowSifter extractors run 84% faster and use 12% of the memory.

Ternary content addressable memories (TCAMs) have become the de facto standard in industry for fast packet classification. Unfortunately, TCAMs have limitations of small capacity, high power consumption, high heat generation, and high cost. The well-known range expansion problem exacerbates these limitations as each classifier rule typically has to be converted to multiple TCAM rules. One method for coping with these limitations is to use compression schemes to reduce the number of TCAM rules required to represent a classifier. Unfortunately, all existing compression schemes only produce prefix classifiers. Thus, they all miss the compression opportunities created by non-prefix ternary classifiers. In this paper, we propose bit weaving, the first non-prefix compression scheme. Bit weaving is based on the observation that TCAM entries that have the same decision and whose predicates differ by only one bit can be merged into one entry by replacing the bit in question with . Bit weaving consists of two new techniques, bit swapping and bit merging, to first identify and then merge such rules together. The key advantages of bit weaving are that it runs fast, it is effective, and it is composable with other TCAM optimization methods as a pre/post-processing routine. We implemented bit weaving and conducted experiments on both real-world and synthetic packet classifiers. Our experimental results show the following: 1) bit weaving is an effective standalone compression technique (it achieves an average compression ratio of 23.6%); 2) bit weaving finds compression opportunities that other methods miss. Specifically, bit weaving improves the prior TCAM optimization techniques of TCAM Razor and Topological Transformation by an average of 12.8% and 36.5%, respectively.

Using Ternary Content Addressable Memories (TCAMs) to perform high-speed packet classication has become the de facto standard in industry because TCAMs facilitate constant time classication by comparing packet elds against ternary encoded rules in parallel. Despite their high speed, TCAMs have limitations of small capacity, large power consumption, and relatively slow access times. One reason TCAM-based packet classiers are so large is the multiplicative eect inherent in representing d-dimensional classiers in TCAMs. To address the multiplicative effect, we propose the TCAM Split architecture, where a d-dimensional classier is split into k = 2 low dimensional classiers, each of which is stored on its own small TCAM. A d-dimensional lookup is split into k low dimensional, pipe-lined lookups with one lookup on each chip. Our experimental results with real-life classiers show that TCAM Split reduces classier size by 84% using only two small TCAM chips, this increases to 93% if we use ve small TCAM chips.

Hamming distance has been widely used in many application domains, such as near-duplicate detection and pattern recognition. We study Hamming distance range query problems, where the goal is to find all strings in a database that are within a Hamming distance bound k from a query string. If k is fixed, we have a static Hamming distance range query problem. If k is part of the input, we have a dynamic Hamming distance range query problem. For the static problem, the prior art uses lots of memory due to its aggressive replication of the database. For the dynamic range query problem, as far as we know, there is no space and time efficient solution for arbitrary databases. In this paper, we first propose a static Hamming distance range query algorithm called HEngined, which addresses the space issue in prior art by dynamically expanding the query on the fly. We then propose a dynamic Hamming distance range query algorithm called HEngined, which addresses the limitation in prior art using a divide-and-conquer strategy. We implemented our algorithms and conducted side-by-side comparisons on large real-world and synthetic datasets. In our experiments, HEnginesuses 4.65 times less space and processes queries 16% faster than the prior art, and HEnginedprocesses queries 46 times faster than linear scan while using only 1.7 times more space.

In this paper, we propose a new opportunistic multicast protocol to improve multicast throughput in Wireless Mesh Networks (WMN). It builds upon opportunistic routing (OR) strategies that have been designed to improve unicast throughput in wireless networks. The key concept in our multicast protocol is a tree backbone. Our tree backbone protocol represents a tradeoff between traditional structured multicast protocols where a complete multicast tree is constructed and unstructured protocols where multicast is treated as a collection of unicasts. Tree backbone selects multiple nodes as intermediate nodes. Each pair of upstream and downstream nodes may be multiple hops away, and packet delivery between them takes advantage of OR. For single-rate WMNs, we show that constructing an efficient tree backbone that minimizes the number of transmissions is NP-hard, and we devise one effective heuristic algorithm for it. For multi-rate WMNs, we investigate the inherent rate-distance tradeoff and propose a Euclidean opportunistic multicast protocol by devising a Euclidean tree backbone as well as an efficient rate selection scheme to minimize the number of transmissions. In our simulations, our tree backbone multicast protocols outperform both the completely structured traditional multicast protocols and the completely unstructured unicast-based protocols augmented with OR in both throughput and delay.

Several range reencoding schemes have been proposed to mitigate the effect of range expansion and the limitations of small capacity, large power consumption, and high heat generation of ternary content addressable memory (TCAM)-based packet classification systems. However, they all disregard the semantics of classifiers and therefore miss significant opportunities for space compression. In this paper, we propose new approaches to range reencoding by taking into account classifier semantics. Fundamentally different from prior work, we view reencoding as a topological transformation process from one colored hyperrectangle to another, where the color is the decision associated with a given packet. Stated another way, we reencode the entire classifier by considering the classifier's decisions rather than reencode only ranges in the classifier ignoring the classifier's decisions as prior work does. We present two orthogonal, yet composable, reencoding approaches: domain compression and prefix alignment. Our techniques significantly outperform all previous reencoding techniques. In comparison to prior art, our experimental results show that our techniques achieve at least five times more space reduction in terms of TCAM space for an encoded classifier and at least three times more space reduction in terms of TCAM space for a reencoded classifier and its transformers. This, in turn, leads to improved throughput and decreased power consumption.

An access control list (ACL) provides security for a private network by controlling the flow of incoming and outgoing packets. Specifically, a network policy is created in the form of a sequence of (possibly conflicting) rules. Each packet is compared against this ACL, and the first rule that the packet matches defines the decision for that packet. The size of ACLs has been increasing rapidly due to the explosive growth of Internet-based applications and malicious attacks. This increase in size degrades network performance and increases management complexity. In this paper, we propose ACL Compressor, a framework that can significantly reduce the number of rules in an access control list while maintaining the same semantics. We make three major contributions. First, we propose an optimal solution using dynamic programming techniques for compressing one-dimensional range-based access control lists. Second, we present a systematic approach for compressing multidimensional access control lists. Last, we conducted extensive experiments to evaluate ACL Compressor. In terms of effectiveness, ACL Compressor achieves an average compression ratio of 50.22 percent on real-life rule sets. In terms of efficiency, ACL runs in seconds, even for large ACLs with thousands of rules.

Recently, the availability of numerous low-cost robotic units (e.g., Packbot, Robomote, and Khepera) has made it possible to massively deploy mobile sensors in a network and use them in a disposable manner. It has been shown that the controlled mobility offered by sensors can be exploited to improve the energy efficiency of a network. In this paper, we study a new problem called max-data mobile relay configuration (MMRC) that finds the positions of a set of mobile sensors, referred to as relays, that maximize the total amount of data gathered by the network during its lifetime. Different from previous controlled mobility approaches, we account for several characteristics of existing practical mobile sensing platforms including limited mobility and the high energy consumption of locomotion. We show that the MMRC problem is surprisingly complex even for a trivial network topology due to the joint consideration of the energy consumption of both wireless communication and mechanical locomotion. We present optimal MMRC algorithms and practical distributed implementations for several important network topologies. Our extensive simulations based on realistic energy models of existing mobile sensing platforms show that our approach can increase the data gathering capacity by a factor of at least 2 in most scenarios. Moreover, our distributed algorithms converge quickly and incur low messaging overhead.

Ternary Content Addressable Memories (TCAMs) have become the de facto standard in industry for fast packet classification. Unfortunately, TCAMs have limitations of small capacity, high power consumption, high heat generation, and high cost. The well-known range expansion problem exacerbates these limitations as each classifier rule typically has to be converted to multiple TCAM rules. One method for coping with these limitations is to use compression schemes to reduce the number of TCAM rules required to represent a classifier. Unfortunately, all existing compression schemes only produce prefix classifiers. Thus, they all miss the compression opportunities created by non-prefix ternary classifiers.

Wireless mesh networks (WMN) have emerged as an economical means for delivering last-mile Internet access. Multicast is a fundamental service in WMNs because it efficiently distributes data among a group of nodes. Multicast algorithms in WMNs are designed to maximize system throughput and minimize delay. Previous work has unrealistically assumed that the underlying WMN is link-homogeneous. We consider one important form of link heterogeneity: different link loss ratios, or equivalently different ETX. We model different link loss ratios by defining a new graph theory problem, HW-SCDS, on an edge-weighted directed graph, where the edge weights model ETX, the reciprocal of link loss ratios. We minimize transmissions in a multicast by computing a minimum HW-SCDS in the edge-weighted graph. We prove HW-SCDS is NP-hard and devise a greedy algorithm for it. Simulations show that our algorithm significantly outperforms the current best WMN multicast algorithm by both increasing throughput and reducing delay.

Recently, wireless sensor networks (WSNs) have become increasingly available for data-intensive applications such as micro-climate monitoring, precision agriculture, and audio/video surveillance. A key challenge faced by data-intensive WSNs is to transmit the sheer amount of data generated within an application's lifetime to the base station despite the fact that sensor nodes have limited power supplies such as batteries or small solar panels. In this paper, we propose to use low-cost disposable mobile relays to reduce the energy consumption of data-intensive WSNs. Different from previous work, our approach does not require complex motion planning of mobile nodes, and hence can be implemented on a number of low-cost mobile sensor platforms. Moreover, we integrate the energy consumption due to both mobility and wireless transmissions into a holistic optimization framework. The optimal relay configuration is shown to depend on both the positions of nodes and the amount of data to be sent. We develop two algorithms that iteratively refine the configuration of mobile relays and converge to the optimal solution. These algorithms have efficient distributed implementations that do not require explicit synchronization. Our simulation results based on realistic energy models obtained from existing mobile and static sensor platforms show that our algorithms significantly outperform the best existing solutions.

Wireless mesh networking is a promising technology for building broadband wireless access networks. However, wireless mesh networks based on CSMA/CA MAC protocols suffer from unfairness and poor QoS support. Using TCP as a rate control mechanism in such networks further exacerbates the problem. Efficient rate allocation and scheduling algorithms that handle both multicast and unicast traffic in wireless mesh networks are needed with the increasing popularity of multicast and multimedia applications. In this paper, we propose a framework that performs both rate allocation and scheduling for unicast and multicast traffic in TDMA-based wireless mesh networks. The rate allocation algorithm is based on network utility maximization. The graph coloring-based scheduling algorithm achieves the allocated rates. Simulation results show that our framework provides guaranteed throughput and low delay for both multicast and unicast traffic. Furthermore, our framework significantly outperforms a previously published framework that has a similar objective.

A firewall is a security guard placed between a private network and the outside Internet that monitors all incoming and outgoing packets. The function of a firewall is to examine every packet and decide whether to accept or discard it based upon the firewall's policy. This policy is specified as a sequence of (possibly conflicting) rules. When a packet comes to a firewall, the firewall searches for the first rule that the packet matches, and executes the decision of that rule. With the explosive growth of Internet-based applications and malicious attacks, the number of rules in firewalls have been increasing rapidly, which consequently degrades network performance and throughput. In this paper, we propose Firewall Compressor, a framework that can significantly reduce the number of rules in a firewall while keeping the semantics of the firewall unchanged. We make three major contributions in this paper. First, we propose an optimal solution using dynamic programming techniques for compressing one-dimensional firewalls. Second, we present a systematic approach to compressing multi-dimensional firewalls. Last, we conducted extensive experiments to evaluate Firewall Compressor. In terms of effectiveness, Firewall Compressor achieves an average compression ratio of 52.3% on real- life rule sets. In terms of efficiency, Firewall Compressor runs in seconds even for a large firewall with thousands of rules. Moreover, the algorithms and techniques proposed in this paper are not limited to firewalls. Rather, they can be applied to other rule-based systems such as packet filters on Internet routers.

Using Ternary Content Addressable Memories (TCAMs) to perform high-speed packet classification has become the de facto standard in industry because TCAMs enable constant time classification by comparing a packet with all rules of ternary encoding in parallel. However, TCAMs have limitations of small capacity, large power consumption and heat generation, and high hardware cost. Although a hardware solution to TCAM limitations is not impossible, TCAMs are unlikely to have hardware breakthroughs because they have pushed silicon to its limit. Furthermore, the number of rules in packet classifiers increases rapidly due to the explosive growth of services deployed on the Internet. In this paper, we propose three approaches, multi-lookup, pipelined-lookup, and packing. The central theme of these three approaches is to minimize the number of TCAM bits used to represent a packet classifier. Reducing TCAM space usage directly addresses the physical limitations of TCAMs. Smaller TCAM implies lower power consumption, less heat generation, less board space, and lower hardware cost. Furthermore, reducing the number of bits used in a TCAM leads to less power consumption and heat generation because the energy consumed by a TCAM grows linearly with the number of bits it uses in storing rules. Our approaches are based on three key observations. First, information stored in TCAMs tends to have high redundancy from an information theory perspective. Specifically, we observe that the same ternary string for a specific field may be repetitively stored in multiple TCAM entries. For example, in the simple two-dimensional packet classifier in Figure 1(a), the strings 001, 010, and 100 from the first

Evolutionary theory explains the origin of complex organismal features through a combination of reusing and extending information from less-complex traits, and by needing to exploit only one of many unlikely pathways to a viable solution. While the appearance of a new trait may seem sudden, we show that the underlying information associated with each trait evolves gradually. We study this process using digital organisms, self-replicating computer programs that mutate and evolve novel traits, including complex logic operations. When a new complex trait first appears, its proper function immediately requires the coordinated operation of many genomic positions. As the information associated with a trait increases, the probability of its simultaneous introduction drops exponentially, so it is nearly impossible for a significantly complex trait to appear without reusing existing information. We show that the total information stored in the genome increases only marginally when a trait first appears. Furthermore, most of the information associated with a new trait is either correlated with existing traits or co-opted from traits that were lost in conjunction with the appearance of the new trait. Thus, while total genomic information increases incrementally, traits that require much more information can still arise during the evolutionary process.

We analyze the shortest remaining processing time (SRPT) algorithm with respect to the problem of scheduling n jobs with release times on m identical machines to minimize total flow time. It is known that SRPT is optimal if m = 1 but that SRPT has a worst-case approximation ratio of Θ(min(log n/m , log Δ)) for this problem, where Δ is the ratio of the length of the longest job divided by the length of the shortest job. It has previously been shown that SRPT is able to use faster machines to produce a schedule as good as an optimal algorithm using slower machines. We now show that SRPT optimally uses these faster machines with respect to the worst-case approximation ratio. That is, if SRPT is given machines that are s ≥ 2 − 1/ m times as fast as those used by an optimal algorithm, SRPT's flow time is at least s times smaller than the flow time incurred by the optimal algorithm. Clearly, no algorithm can offer a better worst-case guarantee, and we show that existing algorithms with similar performance guarantees to SRPT without resource augmentation do not optimally use extra resources.

Packet classification is the core mechanism that enables many networking services on the Internet such as firewall packet filtering and traffic accounting. Using ternary content addressable memories (TCAMs) to perform high-speed packet classification has become the de facto standard in industry. TCAMs classify packets in constant time by comparing a packet with all classification rules of ternary encoding in parallel. Despite their high speed, TCAMs suffer from the well-known range expansion problem. As packet classification rules usually have fields specified as ranges, converting such rules to TCAM-compatible rules may result in an explosive increase in the number of rules. This is not a problem if TCAMs have large capacities. Unfortunately, TCAMs have very limited capacity, and more rules means more power consumption and more heat generation for TCAMs. Even worse, the number of rules in packet classifiers have been increasing rapidly with the growing number of services deployed on the internet. To address the range expansion problem of TCAMs, we consider the following problem: given a packet classifier, how can we generate another semantically equivalent packet classifier that requires the least number of TCAM entries? In this paper, we propose a systematic approach, the TCAM Razor, that is effective, efficient, and practical. In terms of effectiveness, our TCAM Razor prototype achieves a total compression ratio of 3.9%, which is significantly better than the previously published best result of 54%. In terms of efficiency, our TCAM Razor prototype runs in seconds, even for large packet classifiers. Finally, in terms of practicality, our TCAM Razor approach can be easily deployed as it does not require any modification to existing packet classification systems, unlike many previous range expansion solutions.

Phylogenetic trees group organisms by their ancestral relationships. There are a number of distinct algorithms used to reconstruct these trees from molecular sequence data, but different methods sometimes give conflicting results. Since there are few precisely known phylogenies, simulations are typically used to test the quality of reconstruction algorithms. These simulations randomly evolve strings of symbols to produce a tree, and then the algorithms are run with the tree leaves as inputs. Here we use Avida to test two widely used reconstruction methods, which gives us the chance to observe the effect of natural selection on tree reconstruction. We find that if the organisms undergo natural selection between branch points, the methods will be successful even on very large time scales. However, these algorithms often falter when selection is absent.

When examining a new cache structure or replacement policy, the optimal policy is a useful baseline. We prove that finding the optimal schedule is NP-hard for any but the simplest of caches, and that no polynomial-time approximation scheme exists for this problem unless P=NP.

In this paper, we study a combination of the multicast communication problem and the maximum disjoint paths problem. Specifically, we are given a directed tree T rooted at r, and we want to send a message from r to a subset of nodes in T. We accomplish this via a multicast schedule which consists of a number of time steps in which informed nodes deliver the message to uninformed nodes until all destinations have received the message. In each time step, any informed node s may forward the message to one of its uninformed descendant nodes d via the unique directed path, or dipath, p from s to d in ditree T. A multicast schedule is called edge-disjoint if the dipaths used in any time step do not share any edges. We call a multicast schedule a node-disjoint schedule if the dipaths used in any time step are node-disjoint. We show that directed trees can be used to represent source-limited inclusive routing, a realistic class of routing schemes used in popular direct network systems. We then show that node-disjoint multicast schedules in directed trees can be used to closely approximate optimal edge-disjoint multicast schedules. In addition, we show that node-disjoint multicast in directed trees can be reduced to an equivalent broadcast problem in directed trees. We describe an O(n2) greedy algorithm (GA) for performing node-disjoint broadcast in directed trees. The greatest advantages of the GA algorithm are its simplicity and its optimal performance in popular topologies such as meshes, tori, and hypercubes. We also describe an O(n3) algorithm that always produces minimum-length node-disjoint broadcast schedules for directed tree topologies, which can be easily transformed into an algorithm that produces edge-disjoint multicast schedules that are no more than twice the length of an optimal edge-disjoint multicast schedule for an arbitrary topology. © 2000 John Wiley & Sons, Inc.

This article describes our use of competitive analysis and the on-line model of computation in a product development setting; specifically, we use competitive analysis to evaluate on-line scheduling strategies for controlling a new generation of networked reprographic machines (combination printer-copier-fax machines servicing a network) currently being developed by companies such as Xerox Corporation. We construct an abstract machine model, the multipass assembly line, which not only models networked reprographic machines but also models several common manufacturing environments such as a robotic assembly line or a mixed product assembly line. We consider on-line algorithms with finite lookahead because these machines typically have limited knowledge of the future. We first prove some lower bounds on the performance of any on-line algorithm with finite lookahead. We then show that simple greedy algorithms achieve competitive ratios that are close to these general lower bounds. In particular, we show that lookahead improves the competitive ratio of these simple greedy algorithms from approximately 2 (with no lookahead) to being arbitrarily close to 1 (for large lookahead). This implies these simple greedy algorithms are realistic candidates for field use in future reprographic products.

In this paper, we give a general technique for computing optimal multicast calling schedules in any multiprocessor system that utilizes a direct network interconnection structure as long as a few simple conditions are satisfied. Since almost any real system will satisfy these conditions, this result essentially means that multicast can always be performed in [log(d+1)] phases where d is the number of multicast destinations. In particular, previous results on optimal multicast algorithms in specific direct network topologies are simply corollaries of our result.

) Cynthia A. Phillips Cliff Stein y Eric Torng z Joel Wein x Abstract We consider two fundamental problems in dynamic scheduling: scheduling to meet deadlines in a preemptive multiprocessor setting, and scheduling to provide good response time in a number of scheduling environments. When viewed from the perspective of traditional worst-case analysis, no good on-line algorithms exist for these problems, and for some variants no good off-line algorithms exist unless P = NP. We study these problems using a relaxed notion of competitive analysis, introduced by Kalyanasundaram and Pruhs, in which the on-line algorithm is allowed more resources than the optimal off-line algorithm to which it is compared. Using this approach, we establish that several well-known on-line algorithms, that have poor performance from an absolute worst-case perspective, are optimal for the problems in question when allowed moderately more resources. For the optimization of average flow time, these are th...

Paging (caching) is the problem of managing a two-level memory hierarchy in order to minimise the time required to process a sequence of memory accesses. In order to measure this quantity, we define the system parameter miss penalty to represent the extra time required to access slow memory. In the context of paging, miss penalty is large, so most previous studies of on-line paging have implicitly set miss penalty=/spl infin/ in order to simplify the model. We show that this seemingly insignificant simplification substantially alters the precision of derived results. Consequently, we reintroduce miss penalty to the paging problem and present a more accurate analysis of on-line paging (and caching). We validate using this more accurate model by deriving intuitively appealing results for the paging problem which cannot be derived using the simplified model.

The authors present novel fault-tolerance schemes for 2-D systolic implementation of a recursive least squares minimization problem with applications to beamforming problems. They show that the errors can be detected by examining only a few scalars. In the case of the transient errors the technique is self-correcting. The technique can be implemented with negligible algorithm modification and little additional hardware. The simplicity of the method invites its use in future systolic arrays.>