HTTP underpins modern Internet services, and providers enforce quotas to regulate HTTP API traffic for scalability and reliability. When requests exceed quotas, clients are throttled and must retry. Server-side enforcement protects the service. However, when independent clients’ usage counts toward a shared quota, server-only controls are inefficient; clients lack visibility into others’ load, causing their retry attempts to potentially fail. Indeed, retry timing is important since each attempt incurs costs and yields no benefit unless admitted. While centralized coordination could address this, practical limitations have led to widespread adoption of simple client-side strategies like exponential backoff. As we show, these simple strategies cause excessive retries and significant costs. We design adaptive client-side mechanisms requiring no central control, relying only on minimal feedback. We present two algorithms: ATB, an offline method deployable via service workers, and AATB, which enhances retry behavior using aggregated telemetry data. Both algorithms infer system congestion to schedule retries. Through emulations with real-world traces and synthetic datasets with up to 100 clients, we demonstrate that our algorithms reduce HTTP 429 errors by up to 97.3% compared to exponential backoff, while the modest increase in completion time is outweighed by the reduction in errors.

We introduce Hermes, a general-purpose networking architecture built on an overlay of reconfigurable proxies. Hermes delegates networking responsibilities from applications and services to the overlay proxies. It employs a range of proxying and tunneling techniques, utilizes HTTP as its core component, and incorporates assisting components to facilitate service delivery, enhance communication, and improve end-users' experience. To substantiate these benefits, we prototyped Hermes and demonstrated its ability to efficiently address service and communication challenges. We showed that Hermes enables end-to-end solutions for compatibility with legacy applications and protocols and reliable delivery in highly disadvantaged networking conditions. Furthermore, Hermes demonstrated its ability to provide end-to-end, business-logic-driven handling of general IP traffic and to serve as a communication pipeline for Named Data Networking, facilitating the development and adoption of future networking architectures.

This paper systematically evaluates the performance of QUIC/HTTP3 (H3) and TCP/HTTP2 (H2) in proxy-enhanced environments. H3 integrates UDP-based flow-controlled streams, built-in TLS, multiplexing, and connection migration to better support modern web communication. While prior studies show that H3 can outperform or underperform H2 depending on network conditions, the role of proxies and connection migration remains underexplored. We assess a variety of H2 and H3 client implementations across, particularly in lossy networks and proxy setups. Our findings show that proxies can significantly enhance H2 performance, yielding a 90% improvement in single-stream downloads under severe impairments when used with the BBR congestion control algorithm. In contrast, proxies have minimal impact on H3, which maintains consistent performance due to its internal mechanisms. H3 excels under high-loss and high-latency conditions, leveraging connection migration and multiplexing to deliver up to 88.36% improvement in migration scenarios and 81.5% in extreme loss cases. While optimized H2 can match H3 in some settings, H3 is more robust overall, showing less sensitivity to proxies, impairments, and congestion control variations.

We have been working to create a novel and practical software infrastructure to enable networking researchers to develop, evaluate, and demonstrate networked systems, services, and protocols using modern real-world devices and platforms. As a first demonstration of this, we will show an Envoy sidecar overlay network supporting smartphone requested web traffic over a network with intermittent links with real time network monitoring and audience participation.

Linux software routers have many configuration options, most of which have received little attention from researchers. Over time, multiqueue NICs, NUMA architectures, and many changes to the kernel have altered the forwarding landscape. Here we investigate (i) allocation of NIC queues to processing cores, (ii) batch sizes at various layers, (iii) receive and transmit packet steering, and (iv) how FIB performance scales. Our experiments focus on forwarding minimum size packets, which maximize the packet processing stress for the kernel, at 10 Gbps. Our investigation uses Bayesian factor analysis, experimental design techniques, and kernel density estimation to robustly measure each factor's effect on the mean packet forwarding rate and mean RTT. This study does not seek bleeding edge performance. Rather, we elucidate key decisions for packet forwarding performance on a widely used platform. Our results show irqbalance is quite volatile, hyperthreading can provide over a 1 MPPS boost in forwarding performance, larger queue sizes do not improve forwarding but can add non-trivial latency (up to 30 ms), and both receive packet steering and low values of rx-usecs can induce receive livelock.

Named Data Networking (NDN), an information-centric Internet architecture, contains a new architectural component named the strategy layer. This component introduces a new forwarding model, in which a forwarding strategy decides how to forward an Interest packet. In NDN, an application can pair its namespace to use a specific forwarding strategy in the local host, but has no control over the strategies used in remote routers. Despite the central role the forwarding strategy plays, its interaction with applications has not been explored or well understood. In this paper we study and decompose the core mechanisms of a forwarding strategy in NDN. We illustrate how the correctness of some NDN applications can be affected by the coupling between the application design and the strategy decision to retransmit an unsatisfied Interest. This coupling creates challenges for application developers, who must implement their fixed application logic on a variable forwarding mechanism, and can lead to failure of application correctness and performance. We propose a new retransmission abstraction that decouples this strategy mechanism from the application design, and differentiates application Interests from network retransmissions. This allows every application to determine its own retransmission policy. We show that in some use cases the proposed abstraction can maintain continuous traffic flow regardless of the strategy used.

Hash table is one of the most fundamental and critical data structures for membership query and maintenance. However, the performance of a standard hash table degrades greatly when the hash collision is large due to high load factor or unpredictable dynamic membership updates, especially per-packet updates in network processing. In this paper, we shape a hash table from the conventional slim-and-tall style to a wide-and-short style by facilitating an extension of logical cache block. Then, a cache aware hash table (CaHash) is given and explored in detail. Based on an observation that the operation sequences may be in a potential and probabilistic successive order, especially for network applications, a rewritable hash table (RwHash) is finally proposed, which provides two rewritable policies to dynamically move elements within a bucket when updating. Theoretical analysis shows that, no matter what load factor and collision are, RwHash can achieve near-optimal performance the same as the performance when a standard hash table in the case of no collision. Real experiments show that RwHash can achieve 4.10 times speedup in some parameter and even more with different configurations than a standard hash table in the case of heavy collisions. Our approaches are elegantly practical in implementation for both software and hardware.

Name-based forwarding is a core component in information-centric networks. Designing scalable name-based forwarding solutions is challenging because name prefixes are of variable length and the forwarding tables can be much longer than seen with IP. Recently, the speculative forwarding method has been proposed, in which the forwarding structure size is proportional to the information-theoretic differences between the name prefixes rather than their lengths. In this paper, our goal is to enhance name-based forwarding performance with memory-and time-efficient data structures. We first define the string differentiation problem, based on the behavior of speculative forwarding in core networks, and then propose fingerprint-based solutions for both trie-based and hash table-based data structures. We experimentally demonstrate that the proposed solutions reduce the lookup latency and memory requirements. The proposed fingerprint-based Patricia trie decreases the average leaf-node depth and thus reduces the lookup latency. The proposed fingerprint-based hash table design requires only 3.2 GB of memory to store 1 billion names where each name has only one name component, and the measured lookup latency of the software-based single-threaded implementation is 0.29 microseconds. What's more, the distributed forwarding scheme presented in this paper makes name-based forwarding truly scalable.

Collapsed forwarding has long been used in cache systems to reduce the load on servers by aggregating requests for the same content. Named Data Networking (NDN) as a future Internet architecture incorporates this technique through a data structure called Pending Interest Table (PIT). The request aggregation feature suggests that PIT can be viewed as a nonreset time-to-live (TTL) based cache. The Content Store (CS) is a content cache placed in front of the PIT on the NDN forwarding path, so they make up a tandem cache network. To investigate the metrics of interest in this network, like the hit probability for the PIT and the CS, the expected PIT size, non-zero download delay (non-ZDD) should be taken into consideration. Caching policies usually assume zero download delay (ZDD), i.e., request and object arrive simultaneously, and numerous analytical methods have been proposed to study the ZDD caching policies. In this paper, after dissecting the LRU policy, we for the first time propose two LRU variants considering non-ZDD by defining separate operations for the request and object arrivals. When CS adopts the proposed LRU variants, the analysis of the CS-PIT network can still take advantage of the existing models, so the metrics of interest can be computed. Especially, the distribution for the “inter-miss” time of this network can be derived, which has not been achieved by prior works. Finally, the analytical results are verified through simulations.

The majority of analog and digital integrated circuits with built in crystal oscillator use the Gated Pierce design where the oscillator is built around a single CMOS inverting gate. In most applications that require a high level of precision and stability of the performances versus Process, Voltage and Temperature (PVT) variations, this design is not suitable. The inverter cell itself is very sensitive to PVT variations, negatively affecting the overall performances of a crystal oscillator. This paper shows a new Pierce-Gate crystal oscillator based on the constant gm cell, implemented in 28nm CMOS TSMC technology. The oscillator can work with any crystal frequency between 20 MHz and 100 MHz, the power supply is 1.8V and the output is a 50% duty cycle square waveform. Simulations and measurements show that the new designed crystal oscillator is superior in terms of phase noise performances (-123 dBc/Hz at 100 Hz offset at 60 MHz and -163 dBc/Hz at 1MHz offset at 60 MHz), phase noise variation over PVT, Power Supply Rejection Ratio (PSRR), output frequency and output duty cycle stability, and input impedance with respect to the state of the art counterparts. The implemented crystal oscillator is very challenging and suitable for automotive radar applications.

Named Data Networking (NDN), an information-centric Internet architecture, introduces a new forwarding model, in which the forwarding plane can choose between multiple interfaces when forwarding a packet. While the forwarding module brings new opportunities it also introduces challenges when the application's performance or correctness is affected by a conflict between the application design and the assigned forwarding strategy. In this paper we demonstrate the impact of the forwarding strategy decision on the performance and correctness of NDN applications.

Data synchronization-long a staple in le systems-is emerging as a signicant communications primitive. In a distributed system, data synchronization resolves di erences among distributed sets of information. In named data networking (NDN), an information-centric communications architecture, data synchronization between multiple nodes is widely used to support basic services, such as public key distribution, le sharing, and route distribution. While existing NDN synchronization schemes are unctional, their implementations rely on log-based representations of information, which creates a limitation on their performance and scalability. This paper presents iSync, a high performance synchronization protocol for NDN. iSync supports efficient data reconciliation by representing the synchronized datasets using a two-level invertible Bloomfilter (IBF) structure. A set-differences can be found by subtracting a remote IBF from a local IBF. The protocol can obtain multiple differences from a single round of data exchange, and does not require prior context in most application scenarios. We evaluated iSync's performance by comparing it to the CCNx synchronization protocol. Experiments show that iSync is about eight times faster across a range of network topologies and sizes, and that it reduces the number of packets sent by about 90%.

Name prefix lookup is a core building block of information-centric networking (ICN). In ICN hierarchical naming schemes, each packet has a name that consists of multiple variable-length name components, and packets are forwarded based on longest name prefix matching (LNPM). LNPM is challenging because names are longer than IP addresses and the namespace is unbounded. Recently proposed solutions have shown encouraging performance, however, most are optimized for or evaluated with a limited number of URL datasets that may not fully characterize the forwarding information base (FIB).What's more, the worst-case scenarios of several schemes require O(k) string lookups, where k is the number of components in each prefix. Thus, the sustained performance of existing solutions is not guaranteed. In this paper, we present a LNPM design based on the binary search of hash tables, which was originally proposed for IP lookup. With this design, the worst-case number of string lookups is O(log(k)) for prefixes with up to k components, regardless of the characteristics of the FIB. We implemented the design in software and demonstrated 10 Gbps throughput with one billion synthetic longest name prefix matching rules, each containing up to seven components. We also propose level pulling to optimize the average LNPM performance based on the observation that some prefixes have large numbers of next-level suffixes in the available URL datasets.

A Pending Interest Table (PIT) is a core component in Named Data Networking. Scalable PIT design is challenging because it requires per-packet updates, and the names stored in the PIT are long, requiring more memory. As the line speed keeps increasing, e.g., 100 Gbps, traditional hash-table based methods cannot meet these requirements. In this paper, we propose a novel Pending Interest Table design that guarantees packet delivery with a compact and approximate storage representation. To achieve this, the PIT stores fixed-length fingerprints instead of name strings. To overcome the classical fingerprint collision problem, the Interest aggregation feature in the core routers is relaxed. The memory requirement and network traffic overhead are analyzed, and the performance of a software implementation of the proposed design is measured. Our results show that 37 MiB to 245 MiB are required at 100 Gbps, so that the PIT can fit into SRAM or RLDRAM chips.

The CCNx Synchronization protocol is one of the protocols published under the CCNx distribution, and is used to synchronized shared collections of 2 CCNx neighbors. In this paper, we evaluated the performance of the synchronization protocol over different topologies and different network scales.

Most critical security vulnerabilities depend on the OS. If a hacker finds a machine with a vulnerable OS, then he can attack the system. Network administrators can defend against OS-specific attacks if they can find vulnerable machines before hackers do, but physically checking or actively scanning a large network can take time and resources. This paper describes a modification of p0f implemented in the Linux kernel, called k-p0f, which is a tool for this problem. This paper describes the design of k-p0f and compares its performance to p0f with both laboratory-generated and real-world traffic.

Content distribution is a primary activity on the Internet. Name-centric network architectures support content distribution intrinsically. Named Data Networking (NDN), one recent such scheme, names packets rather than end-hosts, thereby enabling packets to be cached and redistributed by routers. Among alternative name-based systems, HTTP is the most significant by any measure. A majority of today's content distribution services leverage the widely deployed HTTP infrastructure, such as web servers and caching proxies. As a result, HTTP can be viewed as a practical, name-based content distribution solution. Of course, NDN and HTTP do not overlap entirely in their capabilities and design goals, but both support name-based content distribution. This paper presents an experimental performance evaluation of NDN-based and HTTP-based content distribution solutions. Our findings verify popular intuition, but also surprise in some ways. In wired networks with local-area transmission latencies, the HTTP-based solution dramatically outperforms NDN, with roughly 10× greater sustained throughput. In networks with lossy access links, such as wireless links with 10% drop rates, or with non-local transmission delays, due to faster link retransmission brought by architectural advantages of NDN, the situation reverses and NDN outperforms HTTP, with sustained throughput increased by roughly 4× over a range of experimental scenarios.

In recent years, operators of large data centers have begun to use BitTorrent to distribute files to large numbers of machines within the data center. The rationale for this trend is clear and well-motivated: BitTorrent is easy to use and enables the scalable distribution of large files to many machines. However, peer-to-peer data distribution applications like BitTorrent are highly configurable, and parameter tuning can have a substantive impact on performance and efficiency. In this work, we use an experimental approach to study the impact of peer-to-peer configuration choices in data center networks. This understanding enables us to improve the performance of Murder, a popular BitTorrent variant used in data centers, by a factor of 5. Moreover, we show that LANTorrent, an alternative tool that uses chain-based distribution rather than swarms, is 12 times faster than Murder.

Modern network intrusion detection systems need to perform regular expression matching at line rate in order to detect the occurrence of critical patterns in packet payloads. While Deterministic Finite Automata (DFAs) allow this operation to be performed in linear time, they may exhibit prohibitive memory requirements. Kumar et al. [2006a] have proposed Delayed Input DFAs (D2FAs), which provide a trade-off between the memory requirements of the compressed DFA and the number of states visited for each character processed, which in turn affects the memory bandwidth required to evaluate regular expressions. In this article we introduce Amortized time − bandwidth overhead DFAs ( A − DFAs ), a general compression technique that results in at most N ( k + 1)/ k state traversals when processing a string of length N , k being a positive integer. In comparison to the D2FA approach, our technique achieves comparable levels of compression with lower provable bounds on memory bandwidth (or greater compression for a given bandwidth bound). Moreover, the A-DFA algorithm has lower complexity, can be applied during DFA creation, and is suitable for scenarios where a compressed DFA needs to be dynamically built or updated. Finally, we show how to combine A-DFA with alphabet reduction and multistride DFAs, two techniques aimed at reducing the memory space and bandwidth requirement of DFAs, and discuss memory encoding schemes suitable for A-DFAs.

Network speeds are increasing and processor core counts rise while processor clock rates stagnate. This has led to both packet processing applications distributing their workload over several cores and to the virtualization of physical systems also using multiple cores. However, these two concepts are at odds with each other as both must take full advantage of multi-core systems for desirable performance. In this paper, we look at the performance considerations of dealing with 10 Gbps traffic rates in worst case loads using a bare-metal system and a virtual appliance model and several difference packet capture methods. We also discuss potential ideas to improve the performance of these virtual systems.

Named Data Networking (NDN) is a recently proposed general- purpose network architecture that leverages the strengths of Internet architecture while aiming to address its weaknesses. NDN names packets rather than end-hosts, and most of NDN's characteristics are a consequence of this fact. In this paper, we focus on the packet forwarding model of NDN. Each packet has a unique name which is used to make forwarding decisions in the network. NDN forwarding differs substantially from that in IP; namely, NDN forwards based on variable-length names and has a read-write data plane. Designing and evaluating a scalable NDN forwarding node architecture is a major effort within the overall NDN research agenda. In this paper, we present the concepts, issues and principles of scalable NDN forwarding plane design. The essential function of NDN forwarding plane is fast name lookup. By studying the performance of the NDN reference implementation, known as CCNx, and simplifying its forwarding structure, we identify three key issues in the design of a scalable NDN forwarding plane: 1) exact string matching with fast updates, 2) longest prefix matching for variable-length and unbounded names and 3) large- scale flow maintenance. We also present five forwarding plane design principles for achieving 1 Gbps throughput in software implementation and 10 Gbps with hardware acceleration.

Peer-to-peer (P2P) applications distribute large files fast. That makes them popular on the Internet and has motivated their use on data center networks. On data center networks, however, these Internet applications waste bandwidth. To fully use available bandwidth, we propose the P2P copy (PCP) application. Results with a prototype show that PCP reduces content distribution times by an order of magnitude.

Network administrators lack the tools they need to understand and react to their changing networks. This makes it difficult for them to make informed, timely decisions regarding network management, capacity planning, and security. These challenges will only increase as networks continue to gain in throughput, become more complex, and encrypt more and more of their traffic. This paper describes the Passive Network Appliance, or PNA, which is our proposed solution to this problem. The PNA provides snapshots of network behavior through time, in a cost-effective manner. The PNA is implemented on commodity hardware and can enforce network policy in real-time at the granularity of network frame arrival. This paper describes the system, and its evaluation in both laboratory and real-world deployments.

High speed networking is a demanding task that has traditionally been performed in dedicated, purpose built hardware or specialized network processors. These platforms sacrifice? exibility or programmability in favor of performance. Recently, there has been much interest in using multi-core general purpose processors, which have the advantages of being easily programmable and upgradeable. We present the design of a high performance packet processing framework that divorces application programming from packet scheduling and mapping.

The recently proposed Named Data Networking (NDN) architecture and the widely deployed HTTP infrastructure both support content distribution in a name-centric fashion. In this paper, we evaluated the content distribution performance of NDN-based and HTTP-based content distribution solutions.

Peer-to-peer (P2P) applications are voracious bandwidth consumers, and ISPs have no effective options for curbing their bandwidth consumption. The Transparent Network Tracker (TnT) is a network device that fills this void: it identifies and monitors P2P traffic on the wire to support applications that control it. In this paper, we describe our TnT prototype and an associated ISP tracker application.

URL matching is used in many network applications, including URL blacklisting, URL-based forwarding and URL shortening services. These applications need fast URL queries and updates, thus requiring an efficient updateable data structure. As the processing power of general-purpose multi-core processors increases, software-based approaches are better able to meet the speed requirements of URL matching. In this paper, we present our preliminary performance study of finite-automata- and hash-based URL matching implementations on commodity PCs. The impacts of the cache and memory allocation methods are discussed.

Internet Service Providers (ISPs) have failed to independently reduce the cost peer-to-peer (P2P) traffic. Traffic- throttling devices increase user download times, and caches store content that may infringe copyright. We propose ISP-Managed P2P (IMP): a transparent peer-discovery service that returns peers favorable to ISPs. Unlike similar services, IMP does not require the direct support of developers who have no incentive to cooperate. This paper covers the design, implementation, and experimental evaluation of our IMP prototype, which reduces costly, cross-ISP traffic by eight times without significantly increasing user download times.

In recent years we have witnessed a proliferation of data structure and algorithm proposals for efficient deep packet inspection on memory based architectures. In parallel, we have observed an increasing interest in network processors as target architectures for high performance networking applications.

Despite their widespread popularity, peer-to-peer (P2P) systems engender continuing controversy. To reduce P2P's high network cost, Internet Service Providers (ISPs) have installed network devices that detect and block P2P traffic. These devices angered subscribers because they also increased download times. For that reason, application developers have begun obfuscating their traffic to avoid ISP-detection. This "cat and mouse" game portends a broader shift. If ISPs remedy the relationship with P2P developers now, developers may cooperate with them to develop network-efficient protocols in the future. Our proposal makes a noteworthy contribution in this direction.

We design and test a multithreaded Snort which uses flow pinning as a major optimization. The insights derived in improving Snort's performance will apply generally to any parallel networking application that uses flow pinning as an optimization.

We describe the implementation of a URL-based forwarding function on a network processor-based programmable router (NPR). URL-based forwarding is an important tool for overlay networks. This paper presents a data path for overlay networks and the effectiveness of a programmable router.

Several algorithms and techniques have been proposed recently to accelerate regular expression matching and enable deep packet inspection at line rate. This work aims to provide a comprehensive practical evaluation of existing techniques, extending them and analyzing their compatibility. The study focuses on two hardware architectures: memory-based ASICs and FPGAs.

Over the last decade, programmable Network Processors (NPs) have become widely used in Internet routers and other network components. NPs enable rapid development of complex packet processing functions as well as rapid response to changing requirements. In the network research community, the use of NPs has been limited by the challenges associated with learning to program these devices and with using them for substantial research projects. This paper reports on an extension to the Open Network Laboratory testbed that seeks to reduce these "barriers to entry" by providing a complete and highly configurable NP-based router that users can access remotely and use for network experiments. The base router includes support for IP route lookup and general packet filtering, as well as a flexible queueing sub-system and extensive support for performance monitoring. In addition, it provides a plugin environment that can be used to extend the router's functionality, enabling users to carry out significant network experiments with a relatively modest investment of time and effort. This paper describes our NP router and explains how it can be used. We provide several examples of network experiments that have been implemented using the plugin environment, and provide some baseline performance data to characterize the overall system performance. We also report that these routers have already been used for ten non-trivial projects in an advanced architecture course where most of the students had no prior experience using NPs.

Nearly all programmable commercial hardware solutions offered for high-speed networking systems are capable of meeting the performance and flexibility requirements of equipment vendors. However, the primary obstacle to adoption lies with the software architectures and programming environments supported by these systems. Shortcomings include use of unfamiliar languages and libraries, portability and backwards compatibility, vendor lock-in, design and development learning curve, availability of competent developers, and a small existing base of software. Another key shortcoming of previous architectures is that either they are not multi-core oriented or they expose all the hardware details, making it very hard for programmers to deal with. In this paper, we present a practical software architecture for high-speed embedded systems that is portable, easy to learn and use, multicore oriented, and efficient.

Regular expression matching is a crucial task in several networking applications. Current implementations are based on one of two types of finite state machines. Non-deterministic finite automata (NFAs) have minimal storage demand but have high memory bandwidth requirements. Deterministic finite automata (DFAs) exhibit low and deterministic memory bandwidth requirements at the cost of increased memory space. It has already been shown how the presence of wildcards and repetitions of large character classes can render DFAs and NFAs impractical. Additionally, recent security-oriented rule-sets include patterns with advanced features, namely back-references, which add to the expressive power of traditional regular expressions and cannot therefore be supported through classical finite automata. In this work, we propose and evaluate an extended finite automaton designed to address these shortcomings. First, the automaton provides an alternative approach to handle character repetitions that limits memory space and bandwidth requirements. Second, it supports back-references without the need for back-tracking in the input string. In our discussion of this proposal, we address practical implementation issues and evaluate the automaton on real-world rule-sets. To our knowledge, this is the first high-speed automaton that can accommodate all the Perl-compatible regular expressions present in the Snort network intrusion and detection system. 1.

Hash tables are extensively used in networking to implement data-structures that associate a set of keys to a set of values, as they provide O(1), query, insert and delete operations. However, at moderate or high loads collisions are quite frequent which not only increases the access time, but also induces non- determinism in the performance. Due to this non-determinism, the performance of these hash tables degrades sharply in the multi-threaded network processor based environments, where a collection of threads perform the hashing operations in a loosely synchronized manner. In such systems, it is critical to keep the hash operations more deterministic. A recent series of papers have been proposed, which employs a compact on-chip memory to enable deterministic and fast hash queries. While effective, these schemes require substantial on- chip memory, roughly 10-bits for every entry in the hash table. This limits their general usability; specifically in the network processor context, where on-chip resources are scarce. In this paper, we propose a novel hash table construction calledPeacockhash, which reduces the on-chip memory by more than 10-folds while keeping a high degree of determinism in performance. This significantly reduced on-chip memory not only makes Peacock hashing much more appealing for the general use but also makes it an attractive choice for the implementation of a hash hardware accelerator on a network processor.

Modern network intrusion detection systems need to perform regular expression matching at line rate in order to detect the occurrence of critical patterns in packet payloads. While deterministic finite automata (DFAs) allow this operation to be performed in linear time, they may exhibit prohibitive memory requirements. In [9], Kumar et al. propose Delayed Input DFAs (D2FAs), which provide a trade-off between the memory requirements of the compressed DFA and the number of states visited for each character processed, which corresponds directly to the memory bandwidth required to evaluate regular expressions.

Deterministic finite automata (DFAs) are widely used to perform regular expression matching in linear time. Several techniques have been proposed to compress DFAs in order to reduce memory requirements. Unfortunately, many real-world IDS regular expressions include complex terms that result in an exponential increase in number of DFA states. Since all recent proposals use an initial DFA as a starting-point, they cannot be used as comprehensive regular expression representations in an IDS.

Data structures representing directed graphs with edges labeled by symbols from a finite alphabet are used to implement packet processing algorithms used in a variety of network applications. In this paper we present a novel approach to represent such data structures, which significantly reduces the amount of memory required. This approach called history-based encoding, execution and addressing (HEXA) challenges the conventional assumption that graph data structures must store pointers of lceillog2nrceil bits to identify successor nodes. We show how the data structures can be organized so that implicit information can be used to locate successors, significantly reducing the amount of information that must be stored explicitly. We demonstrate that the binary tries used for IP route lookup can be implemented using just two bytes per stored prefix (roughly half the space required by Eatherton's tree bitmap data structure) and that string matching can be implemented using 20-30% of the space required by conventional data representations. Compact representations are useful, because they allow the performance-critical part of packet processing algorithms to be implemented using fast, on-chip memory, eliminating the need to retrieve information from much slower off-chip memory. This can yield both substantially higher performance and lower power utilization. While enabling a compact representation, HEXA does not add significant complexity to the graph traversal and update, thus maintaining a high performance.

Hybrid systems consisting of a multitude of different computing device types are interesting targets for high-performance applications. Chip multiprocessors, FPGAs, DSPs, and GPUs can be readily put together into a hybrid system; however, it is not at all clear that one can effectively deploy applications on such a system. Coordinating multiple languages, especially very different languages like hardware and software languages, is awkward and error prone. Additionally, implementing communication mechanisms between different device types unnecessarily increases development time. This is compounded by the fact that the application developer, to be effective, needs performance data about the application early in the design cycle. We describe an application development environment specifically targeted at hybrid systems, supporting data-flow semantics between application kernels deployed on a variety of device types. A specific feature of the development environment is the availability of performance estimates (via simulation) prior to actual deployment on a physical system.

In recent years, overlay networks have become an important vehicle for delivering Internet applications. Overlay network nodes are typically implemented using general purpose servers or clusters. We investigate the performance benefits of more integrated architectures, combining general-purpose servers with high performance Network Processor (NP) subsystems. We focus on PlanetLab as our experimental context and report on the design and evaluation of an experimental PlanetLab platform capable of much higher levels of performance than typical system configurations. To make it easier for users to port applications, the system supports a fast path/slow path application structure that facilitates the mapping of the most performance-critical parts of an application onto an NP subsystem, while allowing the more complex control and exception-handling to be implemented within the programmer-friendly environment provided by conventional servers. We report on implementations of two sample applications, an IPv4 router, and a forwarding application for the Internet Indirection Infrastructure. We demonstrate an 80x improvement in packet processing rates and comparable reductions in latency.

A large body of research literature has focused on improving the performance of longest prefix match IP-lookup. More recently, embedded memory based architectures have been proposed, which delivers very high lookup and update throughput. These architectures often use a pipeline of embedded memories, where each stage stores a single or set of levels of the lookup trie. A stream of lookup requests are issued into the pipeline, one every cycle, in order to achieve high throughput. Most recently, Baboescu et al. [21] have proposed a novel architecture, which uses circular memory pipeline and dynamically maps parts of the lookup trie to different stages.In this paper we extend this approach with an architecture called Circular, Adaptive and Monotonic Pipeline (CAMP), which is based upon the key observation that circular pipeline allows decoupling the number of pipeline stages from the number of levels in the trie. This provides much more flexibility in mapping nodes of the lookup trie to the stages. The flexibility, in turn, improves the memory utilization and also reduces the total memory and power consumption. The flexibility comes at a cost however; since the requests are issued at an arbitrary stage, they may get blocked if their entry stage is busy. In an extreme case, a request may block for a time equal to the pipeline depth, which may severely affect the pipeline utilization. We show that fairly straightforward techniques can ensure nearly full utilization of the pipeline. These techniques, coupled with an adaptive mapping of trie nodes to the circular pipeline, create a pipelined architecture which can operate at high rates irrespective of the trie size.

Auto-Pipe is a tool that aids in the design, evaluation and implementation of applications that can be executed on computational pipelines (and other topologies) using a set of heterogeneous devices including multiple processors and FPGAs. It has been developed to meet the needs arising in the domains of communications, computation on large datasets, and real time streaming data applications. This paper introduces the Auto-Pipe design flow and the X design language, and presents sample applications. The applications include the Triple-DES encryption standard, a subset of the signal-processing pipeline for VERITAS, a high-energy gamma-ray astrophysics experiment. These applications are discussed and their description in X is presented. From X, simulations of alternative system designs and stage-to-device assignments are obtained and analyzed. The complete system permits production of executable code and bit maps that may be downloaded onto real devices. Future work required to complete the Auto-Pipe design tool is discussed.

There is a growing demand for network devices capable of examining the content of data packets in order to improve network security and provide application-specific services. Most high performance systems that perform deep packet inspection implement simple string matching algorithms to match packets against a large, but finite set of strings. owever, there is growing interest in the use of regular expression-based pattern matching, since regular expressions offer superior expressive power and flexibility. Deterministic finite automata (DFA) representations are typically used to implement regular expressions. However, DFA representations of regular expression sets arising in network applications require large amounts of memory, limiting their practical application.In this paper, we introduce a new representation for regular expressions, called the Delayed Input DFA (D2FA), which substantially reduces space equirements as compared to a DFA. A D2FA is constructed by transforming a DFA via incrementally replacing several transitions of the automaton with a single default transition. Our approach dramatically reduces the number of distinct transitions between states. For a collection of regular expressions drawn from current commercial and academic systems, a D2FA representation reduces transitions by more than 95%. Given the substantially reduced space equirements, we describe an efficient architecture that can perform deep packet inspection at multi-gigabit rates. Our architecture uses multiple on-chip memories in such a way that each remains uniformly occupied and accessed over a short duration, thus effectively distributing the load and enabling high throughput. Our architecture can provide ostffective packet content scanning at OC-192 rates with memory requirements that are consistent with current ASIC technology.

Hash tables provide efficient table implementations, achieving O(1), query, insert and delete operations at low loads. However, at moderate or high loads collisions are quite frequent, resulting in decreased performance. In this paper, we propose the segmented hash table architecture, which ensures constant time hash operations at high loads with high probability. To achieve this, the hash memory is divided into N logical segments so that each incoming key has N potential storage locations; the destination segment is chosen so as to minimize collisions. In this way, collisions, and the associated probe sequences, are dramatically reduced. In order to keep memory utilization minimized, probabilistic filters are kept on-chip to allow the N segments to be accessed without in-creasing the number of off-chip memory operations. These filters are kept small and accurate with the help of a novel algorithm, called selective filter insertion, which keeps the segments balanced while minimizing false positive rates (i.e., incorrect filter predictions). The performance of our scheme is quantified via analytical modeling and software simulations. Moreover, we discuss efficient implementations that are easily realizable in modern device technologies. The performance benefits are significant: average search cost is reduced by 40% or more, while the likelihood of requiring more than one memory operation per search is reduced by several orders of magnitude.

Backbone routers typically require large buffers to hold packets during congestion. A thumb rule is to provide a buffer at every link, equal to the product of the round trip time and the link capacity. This translates into Gigabytes of buffers operating at line rate at every link. Such a size and rate necessitates the use of SDRAM with bandwidth of, for example, 80 Gbps for link speed of 40 Gbps. With speedup in the switch fabrics used in most routers, the bandwidth requirement of the buffer increases further. While multiple SDRAM devices can be used in parallel to achieve high bandwidth and storage capacity, a wide logical data bus composed of these devices results in suboptimal performance for arbitrarily sized packets. An alternative is to divide the wide logical data bus into multiple logical channels and store packets into them independently. However, in such an organization, the cumulative pin count grows due to additional address buses which might offset the performance gained. We find that due to several existing memory technologies and their characteristics and with Internet traffic composed of particular sized packets, a judiciously architected data channel can greatly enhance the performance per pin. In this paper, we derive an expression for the effective memory bandwidth of a parallel channel packet buffer and show how it can be optimized for a given number of I/O pins available for interfacing to memory. We believe that our model can greatly aid packet buffer designers to achieve the best performance.

The rapid advancements of networking technology have boosted potential bandwidth to the point that the cabling is no longer the bottleneck. Rather, the bottlenecks lie at the crossing points, the nodes of the network, where data traffic is intercepted or forwarded. As a result, there has been tremendous interest in speeding those nodes, making the equipment run faster by means of specialized chips to handle data trafficking. The Network Processor is the blanket name thrown over such chips in their varied forms. To date, no performance data exist to aid in the decision of what processor architecture to use in next generation network processor. Our goal is to remedy this situation. In this study, we characterize both the application workloads that network processors need to support as well as emerging applications that we anticipate may be supported in the future. Then, we consider the performance of three sample benchmarks drawn from these workloads on several state-of-the-art processor architectures, including: an aggressive, out-of-order, speculative super-scalar processor, a fine-grained multithreaded processor, a single chip multiprocessor, and a simultaneous multithreaded processor (SMT). The network interface environment is simulated in detail, and our results indicate that SMT is the architecture best suited to this environment.

No abstract available.

This paper examines the performance of desktop applications running on the Microsoft Windows NT operating system on Intel x86 processors, and contrasts these applications to the programs in the integer SPEC95 benchmark suite. We present measurements of basic instruction set and program characteristics, and detailed simulation results of the way these programs use the memory system and processor branch architecture. We show that the desktop applications have similar characteristics to the integer SPEC95 benchmarks for many of these metrics, However compared to the integer SPEC95 applications, desktop applications have larger instruction working sets, execute instructions in a greater number of unique functions, cross DLL boundaries frequently, and execute a greater number of indirect calls.