Packet processing is a critical operation in a high-speed router, and in order for this router to achieve memory efficient and fast O(1) lookup operations, Bloom filters (BFs) have been widely used as a packet classifier to reduce expensive hash table accesses. However, it has been identified that a parallel packet classifier (PPC), using all n parallel BFs for a lookup, is neither power nor throughput efficient for high-speed routers. In this paper, we propose a multitiered packet classifier (MPC), both to save power and to improve throughput, with the same memory size as that of a PPC. While a PPC with n BFs consumes Θ(n) BF access complexity for a lookup, our MPC is designed to have the complexity which is probabilistically significantly less than Θ(n). Furthermore, by preprocessing a group of lookups in one cycle in an MPC, we assign each lookup to its associated BF at best effort, and consequently, obtain a higher throughput. With the same reason, as in preprocessing, our MPC design reduces a significant amount of power by preventing accesses to noninvolved BFs during a lookup. In simulation for flow identification with NLANR traces, we observed that the MPC throughput is increased by at most 100 percent, compared to a PPC. Additionally, our MPC shows 4.2 times power efficiency over an equivalent PPC, in terms of power saving.

TCP/IP, the most commonly used network protocol, consumes a significant portion of time in Internet servers. While a wide spectrum of studies has been done to reduce its processing overhead such as TOE and Direct Cache Access, most of them did studies solely from the per-packet perspective and concentrated on the packet memory access overhead. They ignored per-session data TCP Control Block (TCB), which poses a challenge in web servers with a large volume of concurrent sessions.

IP lookup is in the critical data path in a high speed router. In this paper, we propose a new on-chip IP cache architecture for a high performance IP lookup. We design the IP cache along two important axes: cache indexing and cache replacement policies. First, we study various hash performance and employ 2-Universal hashing for our IP cache. Second, coupled with our cache indexing scheme, we present a progressive cache replacement policy by considering Internet traffic characteristics. Our experiments with IP traces show that our IP cache reduces the miss ratio by 15% and a small 32KB IP cache can achieve as high as 2Tbps routing throughput.

Ternary content addressable memories (TCAMs) are becoming very popular due to the simple-to-design IP lookup units included in high-speed routers; they are fast and simple to manage, and they provide a one-clock lookup solution. However, a major drawback of TCAM-based IP lookup schemes lies in their high power consumption. Thus, the rapid increase of routing tables inevitably deteriorates TCAM power efficiency. Although on-chip TCAM minimizers aim for the TCAM power efficiency in a fast time and at a small memory amount, the minimizers are not efficient in a large scale prefix table. In this paper, we present a hash-based on-chip TCAM minimization for a power- and throughput-efficient IP lookup. In a hash-based TCAM minimization (HTM), we convert prefixes into keys and merge keys with a fast hash lookup in an O(nW) complexity, where n is the number of prefixes and W is the number of IP bits. Additionally, by building a forest of merging trees and choosing a subset among them, we can achieve a higher minimization ratio. The simulation with two routing tables shows that our HPM scheme uses 8.6 and 4.0 times fewer computation time and memory, compared to a contemporary on-chip minimizer.

Several challenges in the IP lookup architecture must be addressed for a high-speed forwarding in a large scale routing table: power, memory, and lookup complexity. Hash-based architectures have lookup schemes that are recognized for being both power and memory efficient due to their O(1) lookup, in contrast to other contemporary architectures. In this paper, we propose a novel hash architecture to address these issues by using pipelined Bloom and fingerprint filters for a binary searching in keys. The proposed hash scheme encodes keys' indexes to an on-chip fingerprint table, approximately returns a few indexes in a key query without pointer overhead, and makes a perfect match in an off-chip key table. Due to a memory banking system in pipeline stages, we can achieve O(1) pipelined throughput complexity of insertion, deletion, and query operations. For the IP lookup, a Lulea bitmap with our hash scheme supports a prefix lookup without inflating the numbers of prefixes and next-hops, so that our scalable hash-based scheme can achieve the worst case O(1) IP lookup. The simulation with large scale routing tables shows that our IP lookup scheme offers 4.5 and 50.1 times memory and power efficiencies than other contemporary hash and TCAM schemes, respectively.

Packet classification is a critical data path in a highspeed router. Due to memory efficiency and fast lookup, Bloom filters (BFs) have been widely used for packet classification in a high-speed router. However, in a parallel packet classifier (PPC) of n parallel BFs, using all n BFs for a lookup is not throughput efficient in a high speed router. In this paper, we propose a multi-tiered packet classifier (MPC) for high throughput with the same memory size as a PPC. While a PPC of n BFs needs Theta(n) BF access complexity for a lookup, our MPC is geared to have the complexity which is probabilistically far less than Theta(n). Furthermore, by preprocessing a group of lookups in one cycle, each lookup is assigned to its associated BF at best effort, so that a higher throughput in an MPC is obtained. In simulation for flow identification with NLANR traces, we observed that, at most, 2.0 times more throughput was recorded than a PPC .

Hash tables (HTs) are poorly designed for multiple off-chip memory accesses during packet classification and critically affect throughput in high-speed routers. Therefore, an HT with fast on-chip memory and high-capacity off-chip memory for predictable lookup-throughput is desirable. Both a legacy HT (LHT) and a recently proposed fast HT (FHT) have the disadvantage of memory overhead due to pointers and duplicate items in linked lists. Also, memory usage for an FHT did not consider the bits in counters for fair comparison with an LHT. In this paper, we propose a novel hash architecture called a Multi-predicate Bloom-filtered HT (MBHT) using parallel Bloom filters and generating off-chip memory addresses in the base- 2xnumber system, xisin{1,2,hellip}, which removes the overhead of pointers. Using a larger base of number system, an MBHT reduces on-chip memory size by a factor of log2b2/ log2b1where b1and b2are bases of number system (b2>b1). Compared to an FHT, the MBHT is approximately x(log2n + 4)/(2 log2n) times more efficient for on-chip memory, where n is the number of keys. This results in a significant reduction in the number of off- chip memory accesses. A simulation with a dataset of packets from NLANR shows the on-chip memory reductions by 1.7 and 2 times over an LHT and an FHT are made. Besides, an MBHT of base-16 needs less off-chip memory accesses by 2117 in total URL queries of NLANR, compared to an FHT.

Hash tables (HTs) are poorly designed for multiple memory accesses during IP lookup and this design flow critically affects their throughput in high-speed routers. Thus, a high capacity HT with a predictable lookup throughput is desirable. A recently proposed fast HT (FHT) [20] has drawbacks like low on-chip memory utilization for a high-speed router and substantial memory overheads due to off-chip duplicate keys and pointers. Similarly, a Bloomier filter-based HT (BFHT) [13], generating an index to a key table, suffers from setup failures and static membership testing for keys. In this paper, we propose a novel hash architecture which addresses these issues by using pipelined Bloom filters. The proposed scheme, a hierarchically indexed HT (HIHT), generates indexes to a key table for the given key, so that the on-chip memory size is reduced and the overhead of pointers in a linked list is removed. Secondly, an HIHT demonstrates approximately 5.1 and 2.3 times improvement in on- chip space efficiency with at most one off-chip memory access, compared to an FHT and a BFHT, respectively. In addition to our analyses on access time and memory space, our simulation for IP lookup with 6 BGP tables shows that an HIHT exhibits 4.5 and 2.0 times on-chip memory efficiencies for 160 Gbps router than an FHT and a BFHT, respectively.

Along with energy conservation, it has been a critical issue to maintain a desired degree of coverage in wireless sensor networks (WSNs), especially in a mobile environment. By enhancing a variant of random waypoint (RWP) model, we propose mobility resilient coverage control (MRCC) to assure if-coverage in the presence of mobility. Our basic goals are (1) to elaborate the probability of breaking if-coverage with moving-in and moving-out probabilities, and (2) to issue wake-up calls to sleeping sensors to meet user requirement of if-coverage even in the presence of mobility. Furthermore, by separating the mobility behavior into average and individual, the probability of breaking if-coverage can be precisely calculated, hence reducing the number of sensors to be awakened. Our experiments with NS2 show that MRCC with the individual probability achieves better coverage by 1.4% with 22% fewer numbers of active sensors than that of existing coverage configuration protocol (CCP).

Today's emerging traffic is far removed from the traffic trends seen during the early days of Ethernet technology. As a result, the current IEEE 802.1 standards and its extensions to the spanning tree protocol fall short of providing satisfactory quality of service for traffic which has a significant amount of QoS-sensitive multimedia and VoIP traffic. In the current and near-future scenario of campus-wide networks with significantly large layer-2 clusters and numerous virtual LANs (VLANs), we show significant shortcomings of the basic spanning tree and the multiple spanning tree protocols with regard to QoS. We propose a novel, simple, and yet highly effective enhancement to the multiple spanning tree protocol to achieve a high degree of QoS by keeping in perspective the different characteristics of the various traffic types in the Diffserv framework. We discuss the problems of the current standards and present in detail our proposed extension to overcome them. Our simulation results show good improvements in throughput and significant benefits in delay for all classes of traffic to conclusively prove our claims.

Current traffic patterns are far removed from the traffic trends seen during the early days of Ethernet technology. Therefore, the current IEEE 802.1 standard and its extensions to the spanning tree protocol fall short of providing-satisfactory quality of service for traffic which has a significant amount of QoS-sensitive traffic. In addition, they do not provide a mechanism for stabilizing the traffic load among a whole bridged network where usually the root switch has to handle all the traffic from its child switches. In the current and near-future scenario of switching networks with significantly large layer-2 clusters and numerous VLANs, we show significant shortcomings of the basic spanning tree and the multiple spanning tree protocols with regard to QoS and load balancing. We propose to incorporate a bridge ID scheme of a regional root identifier which is used in multiple spanning tree instance (MSTI) to provide an efficient MSTI building method for QoS and load balancing. Through this scheme, the traffic source of a point-to-multipoint (P2MP) application can set itself as the root of MSTI satisfying the QoS constraint while roots of several regular MSTIs are built in a distributed way. We discuss the problem of building MSTI for P2MP applications and regular MSTIs and present in detail our proposed scheme. Our experiments for two cases show good improvement of QoS in terms of delay and load balancing of the whole bridge network.