Abstract Multi-dimensional packet classification is one of the most important functions to support various services in next generation routers. Both the memory-efficient data structure to support larger rule tables and the hardware architecture to achieve a higher throughput are desired. In this paper, we propose a parallel and pipelined architecture called Set-Pruning Segment Trees with Buckets (SPSTwB) for multi-dimensional packet classification. SPSTwB significantly reduces rule duplication based on a novel partitioning scheme and an efficient bucket merging scheme. The key feature of our proposed architecture is that memory consumption is reduced significantly regardless of the characteristics of various rule tables. In addition, the logic complexity of each pipeline stage is simplified by not storing rule IDs and priorities and thus it can run at a high clock rate. The proposed scheme needs less than 20 bytes per rule for various 100 K rule tables generated by ClassBench. In addition, the proposed scheme supports fast incremental rule update. The proposed pipelined architecture can achieve a throughput of 134 Gbps from the implementation on Xilinx Virtex-7 FPGA device with dual-ported Block RAM.

The equal-cost multi-path routing (ECMP) [4] achieves load balance in data centers network. Without network’s congestion status, ECMP may cause significant imbalance between paths. In this paper, we propose a better congestion aware routing protocol for Software Defined Network (SDN) to provide a better average link utilization. We follow the idea of In-band Network Telemetry (INT) to collect link congestion status in data center networks. Edge switches are responsible for detecting elephant flows by running a heavy hitter detection algorithm. When an elephant flow is reported to the controller by an edge switch, controller will use the collected congestion status to find the least congested path. In order to make the switches forward packets more efficiently and reduce the number of rules in switches’ forwarding table, we adopt label switching. We develop a Programming Protocol-independent Packet Processors (P4) program to design our novel routing scheme, which contains a heavy hitter detection algorithm. We further validate that our heavy hitter detection algorithm can run on Banzai machine. We also write a Python controller to communicate with P4 switches through P4 Runtime protocol. Our experimental results shows that the probing process in CAMP minimizes the bandwidth overhead in data centers. We use Mininet to construct fat-tree topologies and the emulated software P4switches run BMv2. The data mining workload is used to generate the traffic in our experiment. CAMP achieves better FCT compared to ECMP and HULA [6]. Also, the number of routing rules in CAMP maintains the smallest when network grows.

To support fast rule updates in SDN, the Open vSwitch implements Priority Sorting Tuple Space Search (PSTSS) for its packet classifications. Although it has good performance on rule updates, it has a performance concern on table lookups. In contrast, decision tree methods are being actively investigated for high throughput, but they are not able to support fast updates because of rule replications. CutSplit, the state-of-the-art decision tree scheme, provides a novel rule update mechanism by avoiding tree reconstructions. However, its average update time is still two orders of magnitude larger than PSTSS. Meanwhile, existing decision trees are not only unbalanced but also depth unbounded, making them difficult to be optimized on FPGA. In this paper, we present a new decision tree scheme called TabTree, which achieves high performance on both lookups and updates. By mapping rules into tree nodes dynamically, a very limited number of balanced trees with bounded depths can be generated without the trouble of rule replications. Experimental results show that, TabTree has comparable update performance to PSTSS, but it outperforms PSTSS significantly in terms of number of memory accesses for packet classification. Additionally, TabTree is more practical for implementations on FPGA.

Packet classification is one of the important functions in today’s high-speed Internet routers. Many existing FPGA-based approaches can achieve a high throughput but cannot accommodate the memory required for large rule tables because on-chip memory in FPGA devices is limited. In this paper, we propose a high-throughput and low-cost pipelined architecture using a new recursive endpoint-cutting (REC) decision tree. In the software environment, REC needs only 5–66% of the memory needed in Efficuts for various rule tables. Since the rule buckets associated with leaf nodes in decision trees consume a large portion of total memory, a bucket compression scheme is also proposed to reduce rule duplication. Based on experimental results on Xilinx Virtex-5/6 FPGA, the block RAM required by REC is much less than the existing FPGA-based approaches. The proposed parallel and pipelined architecture can accommodate various tables of 20 K or more rules, in the FPGA devices containing 1.6 Mb block RAM. By using dual-ported memory, throughput of beyond 100 Gbps for 40-byte packets can be achieved. The proposed architecture outperforms most FPGA-based search engines for large and complex rule tables.

Multibit trie-based pipelines for IP lookups have been demonstrated to be able to achieve the throughput of over 100 Gbps. However, it is hard to store the entire multibit trie into the on-chip memory of reconfigurable hardware devices. Thus, their performance is limited by the speed of off-chip memory. In this paper, we propose a new pipeline design called LayeredTrees that overcomes the shortcomings of the multibit trie-based pipelines. LayeredTrees pipelines the multi-layered multiway balanced prefix trees based on the concept of most specific prefixes. LayeredTrees is optimized to fit the entire routing table into the on-chip memory of reconfigurable hardware devices. No prefix duplication is needed and each${\mbi {W}}$-bit prefix is encoded in a (${\mbi {W}} + {\bf 1}$)-bit format to save memory. Assume the minimal packet size is 40 bytes. Our experimental results on Virtex-6 XC6VSX315T FPGA chip show that the throughputs of 33.6 and 120.8 Gbps can be achieved by the proposed single search engine and multiple search engines running in parallel, respectively. Furthermore, the impact of update operations on the search performance is minimal. With the same FPGA device, an IPv6 routing table of 290,503 distinct entries can also be supported.

Ternary content-addressable memory (TCAM) is a simple hardware device for fast IP lookups that can perform a lookup per cycle. However, prefixes may be inserted into or deleted from the TCAM because of changes in Internet topology. Traditional TCAM coprocessors maintain the enclosure relationship among prefixes by using an extended binary trie and perform TCAM movements based on an update algorithm (e.g., CAO_OPT) which runs on a local CPU to maintain the speed and correctness of the TCAM search process. In this paper, we propose a memory-efficient TCAM coprocessor architecture for updates that require only small memory size compared with the extended binary trie. The average number of TCAM movements per update is almost the same as that of CAO_OPT. However, the time to compute how to move TCAM entries in the proposed TCAM coprocessor is less than that in CAO_OPT. Only a small part of total TCAM search cycles is used to complete our update process. The proposed TCAM architecture can also be made smaller and faster because large off-chip memory for the extended binary trie and a local CPU are no longer necessary.

Ternary Content Address Memory (TCAM) becomes a popular hardware device for storing the packet classifiers due to the advantages of high and deterministic lookup performance. However, managing the filter set in TCAM is quite complicated when filters need to be updated. To ensure the correctness of search results, it is required to obtain the right position in TCAM for storing the new filter. In addition, some filters need to be moved to other positions for maintaining the correct filter overlapping relationship based on their priorities. Normally, an auxiliary data structure is used to compute how to insert or delete a filter into/from TCAM. However, this auxiliary data structure is usually complicated and large. Instead of maintaining an auxiliary data structure, in this paper, we propose an efficient TCAM update scheme that simply uses a very small portion of TCAM search cycles to compute how to move the filters related to the filter to be inserted or deleted. Therefore, a large amount of memory for storing the auxiliary data structure along with the local CPU for updates can be avoided. In addition, our simulation results show that the proposed update scheme needs less number of TCAM movements than the existing CoPTUA update scheme.

Recently, research community has drawn lots of attentions in the router virtualization that allows multiple virtual router instances running on the same physical router platform. Thus, the virtualized router should be able to handle packets from different virtual networks. Once the multiple virtual routing tables are merged, memory requirement can be reduced due to the common entries among virtual routing tables. Many previous works use trie-based methods to merge the virtual routing tables. In this paper, we propose a range-based merging method. The data structure is based on the dynamic multiway segment tree (DMST) that is implemented with standard B-tree structure. As our experimental results show, faster lookup speed and incremental update can be achieved. The proposed method performs much better than the trie-based ones in lookup speed and scalability, and has similar memory consumption.

A root cause is a source of software defect, whose removal decreases or removes the defect. A root cause of software defect is injected into the software by software engineers during the development process. One of the main concerns of the software team leader, such as the project manager, is to determine who injected various root causes of the defects into the software and when these have been injected. In this paper, a cost-benefit scheme is presented, which allows a software team to determine skill weakness and improve team capability. The scheme provides effective in-process feedback based on the causal analysis of software defects. The proposed analysis scheme includes orthogonal root cause definitions, role-based root cause types, and gradational correction actions. In the experiment, the projects of a distributed health-care system are used to verify the efficiency of the proposed scheme. The results show that the root cause ratios (RCR) are 33.8%, 30.6%, 21.9%, 10.7%, and 3.0% in design, implementation, analysis, business and deployment, respectively. The defects in the projects mainly occurred during the design and implementation phases of the projects. Correction activities to enhance the designers’ skills, such as exception handling (40.5%) and DB/data schema (25.0%), are the top priorities that must be addressed by the software team. The findings can help the team leader to determine methods to improve these weaknesses.

An efficient ternary content addressable memory (TCAM) encoding scheme using a binary reflected Gray code (BRGC) and the concept of elementary intervals is presented for efficiently storing arbitrary ranges in TCAM. The proposed layered BRGC range encoding scheme (L-BRGC) groups ranges into BRGC range sets in which each range can be encoded into a single ternary vector. The results of experiments performed on real-life and synthesized rule tables show that L-BRGC consumes less TCAM than all the existing range encoding schemes for all rule tables, except that the direct conversion scheme (EIGC) using elementary intervals and BRGC codes performs best for a small real-life ACL rule table.

Packet classification is an important building block of the Internet routers for many network applications. In this paper, we propose a scheme called Layer Partitioned Search Tree (LPST) to solve multi-field packet classification problem. LPST improves the traditional decision tree based schemes (e.g. Hyper Cuts and EffiCuts) by reconstructing the leaf nodes of the decision tree as an approximately balanced search tree. The rules may be stored not only in the buckets of leaf nodes but also in the internal nodes of LPST. Thus, searches on LPST may be completed immediately without searching all the buckets on the path to some leaf node if the packet already matches an internal node. The experimental results show that LPST requires less memory storage even if LPST categorizes the rules by two fields to reduce rule duplication rather than five fields in EffiCuts. Besides, in terms of number of memory accesses, LPST is better than Hyper Cuts and EffiCuts.

Packet classification is an important topic for high speed routers nowadays. There are many packet classification algorithms based on decision tree like Hicuts, Hyper cuts and Hyper split. Because Hicuts and Hyper cuts divides the rule sets by cutting the address space into equal-sized subspaces, their cutting efficiency is not good. Although Hyper split proposed a good end-point-based cutting scheme, the resulting tree depth is still very high. In this paper, we propose a multi-dimensional cutting algorithm to significantly reduce the decision tree depth and a multi-layered scheme to dramatically reduce the usage of memory. Our experimental results show that the proposed layered scheme needs much less memory than Hyper split for Firewall and IPC rule tables with a factor of 2 to 106 improvement while the proposed layered scheme needs a little more memory than Hyper split for some of ACL tables. In addition, in terms of number of memory accesses, the proposed layered scheme and Hyper cuts are better than Hicuts and Hyper split for all tables while the proposed layered scheme is better than Hyper cuts for ACL and Firewall tables. In terms of number of memory accesses, our layered cutting scheme and Hyper cuts perform equally well for small rule tables. But, in larger rule tables, the proposed layered cutting scheme has better performance.

Nowadays, multi-field packet classification is one of the most important technologies to support various services in next generation routers. In this paper, we propose a segment tree based parallel SRAM-based pipelined architecture called Set Pruning Segment Trees (SPST) for multi-dimensional packet classification. For solving the memory blowup problem, a grouping scheme called Partition by Length (PL) is used to reduce the rule duplications in SPST. Additionally, we also propose an optimization called Set Pruning Multi-way Segment Trees (SPMST) to reduce the tree level and hardware cost. The key feature of our proposed architecture is that memory consumption is reduced significantly regardless of the characteristics of various rule tables. The proposed pipelined architecture can achieve a throughput of 89.4 Gbps for minimum sized packets with dual port memory on Xilinx Virtex-5 FPGA device.

Packet classification has wide applications such as unauthorized access prevention in firewalls and Quality of Service supported in Internet routers. The classifier containing pre-defined rules is processed by the router for finding the best matching rule for each incoming packet and for taking appropriate actions. Although many software-based solutions had been proposed, high search speed required for Internet backbone routers is not easy to achieve. To accelerate the packet classification, the state-of-the-art ternary content-addressable memory (TCAM) is a promising solution. In this paper, we propose an efficient multi-field range encoding scheme to solve the problem of storing ranges in TCAM and to decrease TCAM usage. Existing range encoding schemes are usually single-field schemes that perform range encoding processes in the range fields independently. Our performance experiments on real-life classifiers show that the proposed multi-field range encoding scheme uses less TCAM memory than the existing single field schemes. Compared with existing notable single-field encoding schemes, the proposed scheme uses 12% ~ 33% of TCAM memory needed in DRIPE or SRGE and 56% ~ 86% of TCAM memory needed in PPC for the classifiers of up to 10k rules.

Service systems used for various applications in home automation and security require estimating the locations precisely using certain sensors. Serving a mobile user automatically by sensing his/her locations in an indoor environment is considered as a challenge. However, indoor localization cannot be carried out effectively using the Global Positioning System (GPS). In recent years, the use of Wireless Sensor Networks (WSNs) in locating a mobile object in an indoor environment has become popular. Some physical features have also been discussed to solve localization in WSNs. In this paper, we inquire into received signal strength indication (RSSI)-based solutions and propose a new localization scheme called the closer tracking algorithm (CTA) for indoor localization. Under the proposed CTA, a mechanism on mode-change is designed to switch automatically between the optimal approximately closer approach (ACA) and the real-time tracking (RTT) method according to pre-tuned thresholds. Furthermore, we design a mechanism to move reference nodes dynamically to reduce the uncovered area of the ACA for increasing the estimation accuracy. We evaluate the proposed CTA using ZigBee CC2431 modules. The experimental results show that the proposed CTA can determine the position accurately with an error distance less than 0.9 m. At the same time, the CTA scheme has at least 87% precision when the distance is less than 0.9 m. The proposed CTA can select an adaptive mode properly to improve the localization accuracy with high confidence. Moreover, the experimental results also show that the accuracy can be improved by the deployment and movement of reference nodes.

Network Intrusion Detection System (NIDS) is a system which can detect network attacks resulted from worms and viruses on the Internet. An efficient pattern matching algorithm plays an important role in NIDS. There have been many proposed methods for pattern matching algorithms. Traditionally, the multi-character NFA that is capable of matching multiple characters per cycle can be built by duplicating entire circuit of 1-character architecture. In this paper, we propose a pre-processing based architecture to improve the original multi-character architecture. The design of the proposed architecture and its implementation in FPGA are described in details. Our simulation results show that the proposed architecture performs better than all the existing Brute-Force based approaches in terms of the throughput and the slice utilization. Specifically, the proposed architectures of 2-character and 4-character designs can achieve the throughputs of 4.68 and 7.27 Gbps and the slice utilization of 2.86 and 2.10 in terms of char/slice, respectively.

Packet classification problem has received much attention and continued to be an important topic in recent years. In packet classification problem, each incoming packet should be classified into flows according to a set of pre-defined rules. Grid-of-tries (GoT) is one of the traditional algorithmic schemes for solving 2-dimensional packet classification problem. The advantage of GoT is that it uses the switch pointers to avoid backtracking operation during the search process. However, the primary data structure of GoT is base on binary tries. The traversal of binary tries decreases the performance of GoT due to the heights of binary tries are usually high. In this paper, we propose a scheme called GST (Grid of Segment Trees). GST modifies the original GoT by replacing the binary tries with segment trees. The heights of segment trees are much shorter than those of binary tries. As a result, the proposed GST can inherit the advantages of GoT and segment trees to achieve better performance. Experiments conducted on three different kinds of rule tables show that our proposed scheme performs better than traditional schemes, such as hierarchical tries and grid-of-tries.

Multi-field Packet classification is the main function in high-performance routers. The current router design goal of achieving a throughput higher than 40 Gbps and supporting large rule sets simultaneously is difficult to be fulfilled by software approaches. In this paper, a set pruning trie based pipelined architecture called Set Pruning Multi-Bit Trie (SPMT) is proposed for multi-field packet classification. However, the problem of rule duplications in SPMT that may cause a memory blowup must be solved in order to implement SPMT with large rule sets in FPGA devices consisting of limited on-chip memory. We will propose two rule grouping schemes to reduce rule duplications in SPMT. The first scheme called Partition by Wildcards (PW) divides the rules into subgroups based on the positions of their wildcard fields. The second scheme called Partition by Length (PL) rules partitions the rules into subgroups according to their prefix lengths. Based on our performance experiments on Xilinx Virtex-5 FPGA device, the proposed pipeline architecture can achieve a throughput of over 100 Gbps with dual port memory. Also, the rule sets of up to 10k rules can be fit into the on-chip memory of Xilinx Virtex-5 FPGA device.

With the evolution of the Internet, current routers need to support a variety of emerging network applications while the high packet processing rate is still guaranteed. As a result, the network processor has become a promising solution for network devices due to its computation capability and programming flexibility. However, developing the network applications on network processors is not easy. How to efficiently program multiple processing elements and utilize various memory modules as well as the hardware resources on network processors are always challenges. In this paper, we investigate several optimization issues and programming techniques that should be considered by the developers to achieve higher packet processing rate on network processors. We use an existing packet classification scheme called hierarchical binary prefix search (HBPS) [1] as the benchmark to test and evaluate these optimization techniques. The experiments conducted on Intel IXP2400 network processor show that the overall performance of HBPS can be improved about 42% while these techniques are adopted.

A dynamic multiway segment tree (DMST) is proposed for IP lookups in this paper. DMST is designed for dynamic routing tables that can dynamically insert and delete prefixes. DMST is implemented as a B-tree that has all distinct end points of ranges as its keys. The complexities of search, insertion, deletion, and memory requirement are the same as the existing multiway range tree (MRT) and prefix in B-tree (PIBT) for prefixes. In addition, a pipelined DMST search engine is proposed to further speed up the search operations. The proposed pipelined DMST search engine uses off-chip SRAMs instead of on-chip SRAMs because the capacity of the latter is too small to hold large routing tables and the cost of the latter is too expensive. By utilizing current FPGA and off-chip SRAM technologies, our proposed five-stage pipelined search engine can achieve the worst case throughputs of 33.3 and 41.7 million packets per second (Mpps) with 144-bit and 288-bit wide SRAM blocks, respectively. Furthermore, a straightforward extension of the pipelined search engine with multiple independent off-chip SRAMs can achieve the throughput of 200 Mpps which is equivalent to 102 Gbps for minimal Ethernet packets of size 64 bytes.

This paper deals with the traditional IP address lookup problem with fast updates. We propose a B-tree data structure, called MMSPT (multiway most specific prefix tree), which is constructed by using the most specific prefixes in routing tables. MMSPT arranges the most specific prefixes as the keys in B-tree. Unlike the previous schemes, every prefixes in routing tables is stored exactly once in our MMSPT. For a routing table of n prefixes, MMSPT requires O(n) memory, and the time for search, insertion and deletion operations are O(logmn), O(mlogmn), and O(mlogmn), respectively (m is the order of the B-tree). Our experimental results conducted by using five real IPv4 routing tables show that MMSPT outperforms two existing B-tree data structures, PIBT (prefix in B-tree) and MRT (multiway range tree), in all aspects. Moreover, since the complexities of MMSPT is not subject to the length of IP addresses, the proposed MMSPT can be easily extended to fit the IPv6.

IP address lookup is one of the most important functionalities in the router design. To meet the requirements in high speed routers consisting of line-cards with 40 Gbps transfer rates, researchers usually take lookup/update speed, storage requirement, and scalability into consideration when designing a high performance forwarding engine. As a result, hardware-based solutions are often used to develop a high speed router nowadays. In this paper, we develop a FPGA-based pipelined forwarding engine which focuses on reducing the update overhead. The proposed scheme partitions the routing table into several disjoint groups. The prefix which resides in the same group is interleaving stored into several memory modules to ensure the parallel comparison at the comparison stage. With the pipeline enabled, the throughput of the design can achieve the speed of OC-768. The update overhead can also be reduced.

Packet classification has continued to be an important research topic for high-speed routers in recent years. In this paper, we propose a new packet classification scheme based on the binary range and prefix searches. The basic data structure of the proposed packet classification scheme for multidimensional rule tables is a hierarchical list of sorted ranges and prefixes that allows the binary search to be performed on the list at each level to find the best matched rule. We also propose a set of heuristics to further improve the performance of the proposed algorithm. We test our schemes by using rule tables of various sizes generated by ClassBench and compare them with the existing schemes, EGT, EGT-PC, and HyperCuts. The performance results show that in a test using a 2D segmentation table, the proposed scheme not only performs better than the EGT, EGT-PC, and HyperCuts in classification speed and memory usage but also achieves faster table update operations that are not supported in the existing schemes.

Network intrusion detection system (NIDS) is a system developed for identifying attacks by using a set of rules. NIDS is an efficient way to provide the security protection for today's Internet. Pattern match algorithm plays an important role in NIDS that performs searches against multiple patterns for a string match. Pattern matching is a computationally expensive task. Traditional software-based NIDS solutions usually can not achieve a high-speed required for ever growing Internet attacks. In order to satisfy high-speed packet content inspection, hardware-implementable pattern match algorithm is required. In this paper, we propose a hardware-based pattern match architecture that employs a multi-character processor array. The proposed multi-character processor array is a parallel and pipelined architecture which can process multiple characters of the input stream per cycle. The proposed architecture can reduce a lot of unnecessary computations and thus it is power efficient. We use snort pattern sets and DEFCON packet traces to perform our simulations. Our experiment results show that, with a 3-character processor array, we can reduce 83% of the computations compared with the brute force approach.

Traditional cache invalidation schemes are not suitable to be employed in wireless environments due to the affections of mobility, energy consumption, and limited bandwidth. Cache invalidation report (IR) is proposed to deal with the cache consistency problem. However, the main drawback of IR-based schemes is the long latency of data access because the mobile hosts (MHs) need to wait next IR interval for cache invalidation when the cache hit happens. In this paper, we propose a dynamic invalidation report (DIR) to reduce the latency of data access when the MHs query data. DIR contains an early cache validation mechanism by utilizing the validation messages. Therefore, the MHs can verify their cached data as soon as possible. Next, we design a predictive method to dynamically adjust IR interval to further reduce the latency called DIR-AI (DIR with adjustable interval) scheme. Finally, we evaluate the performance of the DIR and DIR-AI and compare them with the existing invalidation report schemes by using NS2 (network simulator). The experimental results show that DIR reduces averagely 54.3% and 34.3% of latency; DIR-AI reduces averagely 57.35 and 38.6% of latency compared with TS (TimeStamp) and UIR (updated IR) schemes respectively.

With the increasing growth of the Internet, the explosion of attacks and viruses significantly affects the network security. Network intrusion detection system (NIDS) is developed to identify these network attacks by a set of rules. However, searching for multiple patterns is a computationally expensive task in NIDS. Traditional software-based solutions can not meet the high bandwidth demanded in current high-speed networks. In the past, the pre-filtering designed for NIDS is an effective technique that can reduce the processing overhead significantly. A FNP- like TCAM searching engine (FTSE) is an example that uses an 2-stage architecture to detect whether an incoming string contains patterns. In this paper, we propose two techniques to improve the performance of FTSE that utilizes ternary content addressable memory (TCAM) as pre-filter to achieve gigabit performance. The first technique performs the w-byte suffix pattern match instead of using w-byte prefix. The second technique finds the matching results from all groups rather than first group. We finally present the simulation result using Snort pattern set and DEFCON packet traces.

This short report first indicates a design flaw in the contention resolver unit proposed in [Akhbarizadeh et al., 2007] and then proposes an improved design which is simpler and faster.

Packet classification is an enabling function in Internet routers for a variety of Internet applications. In order to classify Internet packets into flows, Internet routers must perform searches over a set of filters using multiple fields of the packet as the search key. Because of its speed and simple filter management the Ternary Content Addressable Memory (TCAM) is currently the dominant hardware solution for IP lookups, i.e., a one-dimensional packet classification. To make TCAM the solution for the multi-dimensional packet classification, efficient methods that store the range fields of the classification tables in TCAM are needed. In this paper, we propose a set of novel range encoding schemes based on Gray code. Many range-encoding techniques are used to improve the existing elementary interval- based range encoding schemes. The present experiment's results show that the proposed Gray code-based schemes consume less TCAM storage space than the existing schemes.

In this paper, we develop a segment tree data structure for solving dynamic table lookup problems. The proposed dynamic segment tree (DST) uses all of the distinct end points of ranges as the keys based on a new range end point scheme. The new end point scheme generates fewer end points than the traditional end point scheme. DST is implemented as a balanced binary search tree augmented with a range set in each node. The performance of accessing and updating the ranges stored in each node is improved by an efficient range set data structure that combines the priority queue and the interval tree. Based on the proposed data structures, the time complexities of search, insertion, and deletion in a set of N arbitrary ranges are O(log N), O(log N times log Max), and O(Max times log N times log Max), respectively, where Max is the maximum number of ranges covering any address. In practical routing tables, Max is a small constant (six for the routing tables we tested). The memory requirement for DST is O(N log N). The experimental results using real Internet Protocol version 4 (IPv4) routing tables show that both the DST and prefix binary tree on binary tree (PBOB) by Lu et al. (2004) perform much better than the multiway range tree (MRT) by Warkhede et al. (2004) and prefix in B-tree (PIBT) by Lu et al. (2005) in terms of update speed and memory consumption, but DST performs much better than PBOB and a little slower than MRT and PIBT in terms of search speed

In the divisible load distribution, the classic methods on linear arrays divide the computation and communication processes into multiple time intervals in a pipelined fashion. Li (2003) has proposed a set of improved algorithms for linear arrays which can be generalized to k-dimensional meshes. In this paper, we first propose the algorithm M (multi-installment) that employs the multi-installment technique to improve the best algorithm Q proposed by Li. Second, we propose the algorithm S (start-up cost) that includes the computation and communication start-up costs in the design. While the asymptotic speedups of our algorithms M and S derived from the closed-form solutions are the same as algorithm Q, our algorithms approach the optimal speedups considerably faster than algorithm Q as the number of processors increases. Finally, we combine algorithms M and S and propose the algorithm MS. While algorithm MS has the same the asymptotic performance as algorithms Q and S, it achieves a better speedup when the load to be processed is very large and the number of processors is fixed or when the load to be processed is fixed and the number of processors is small.

As the demand for high-quality Internet increases, emerging network applications are spurring the need for faster, feature-rich, and cost-effective routers. Multifield packet classification in routers has been a computation-intensive data path function for software implementation. Therefore, solutions for packet classification based on hardware design, such as Ternary Content Addressable Memory (TCAM), are necessary to sustain gigabit line processing rate. Traditionally, TCAMs have been designed for storing prefixes. However, multifield packet classification usually involves two fields of arbitrary ranges that are TCP/IP layer 4 source and destination ports. Storing ranges in TCAMs relies on decomposing each individual range into multiple prefixes, which leads to range-to-prefix blowout. To reduce the total number of prefixes needed to represent all ranges, this paper proposes a 2-level TCAM architecture and two range-to-prefix conversion schemes. In the first proposed scheme, designed for disjoint ranges, the maximum number of entries needed in TCAM is 2m-1 for m disjoint ranges. In the second proposed scheme, designed for contiguous ranges, only m TCAM entries are needed. In a general case of n arbitrary ranges, all ranges can first be converted into disjoint ranges or contiguous ranges and then the proposed algorithms can be applied. As a result, only 4n-3 TCAM entries are needed for the disjoint ranges and only 2n+1 TCAM entries are needed for contiguous ranges. This paper also proposes insertion and deletion algorithms to accommodate incremental changes to the range sets. The experiments made show that the proposed range-to-prefix conversion schemes perform better than the existing schemes in terms of the number of required TCAM entries and execution time for range update operations.

More and more users use mobile devices to retrieve dynamic Web pages in the wireless networks. Caching dynamic pages becomes very important due to the power constraint of mobile devices. In this paper, we first introduce a framework to cache and manage the dynamic Web pages on the server side such that these dynamic pages can also be cached in the mobile devices. Then we propose a stateful IR-based approach, which only records two numbers, the number of Web pages updated and the number of Web pages updated and also queried after they are updated on the server in an IR interval. Recording these two numbers dramatically reduces the IR size. The experiments show that our proposed approach combined with the timestamp and UIR algorithms consumes the power around 40 /spl sim/ 47% less than the original timestamp and UIR. Also, our method performs better than the perfect server that has the full knowledge of the contents stored in all the mobile client's caches in terms of power consumption.

As the demand for high bandwidth on the Internet increases, it is required to build next generation routers with the capability of forwarding multiple millions of packets per second. Reducing the required memory size of the forwarding table is a possible solution since small forward table can be integrated into the application specific integrated circuit (ASIC). In this paper a hash technique is developed to make the IP forwarding table as small as possible. The experiments show that the required memory size of the proposed scheme is smaller than other existing schemes for a large routing table.