Line-rate data traffic monitoring in high-speed networks is essential for network management. To satisfy the line-rate requirement, one can leverage multi-core architectures to parallelize traffic monitoring so as to improve information processing capabilities over traditional uni-processor architectures. Nevertheless, realizing the full potential of multi-core architectures still needs substantial work, especially in the face of the ever-increasing volume and complexity of network traffic. This paper addresses the issue through the design of a lock-free, cache-efficient synchronization mechanism that serves as a basic building block for a general class of multithreaded, multi-core traffic monitoring applications. We embed the synchronization mechanism into MCRingBuffer, a multi-core shared ring buffer that provides fast data accesses among threads running in different cores. MCRingBuffer allows concurrent lock-free data accesses and improves the cache locality of accessing the control variables that are used for thread synchronization. Through extensive evaluation on an Intel Xeon multi-core machine, we show that MCRingBuffer achieves a throughput gain of up to 5× over existing lock-free ring buffers. Finally, we present a parallel traffic monitoring prototype that is built upon MCRingBuffer, and demonstrate via trace-driven simulation how MCRingBuffer facilitates packet processing at line rate.

We propose MCRingBuffer, a lock-free, cache-efficient shared ring buffer that provides fast data accesses among threads running in multi-core architectures. MCRingBuffer seeks to reduce the cost of inter-core communication by allowing concurrent lock-free data accesses and improving the cache locality of accessing control variables used for thread synchronization. Evaluation on an Intel Xeon multi-core machine shows that MCRingBuffer achieves a throughput gain of up to 4.9x over existing concurrent lock-free ring buffers. A motivating application of MCRingBuffer is parallel network traffic monitoring, in which MCRingBuffer facilitates multi-core architectures to process packets at line rate.

The third-generation (3G) wide area wireless networks and 802.11 local area wireless networks possess complementary characteristics. 3G networks promise to offer always-on, ubiquitous connectivity with relatively low data rates. 802.11 offers much higher data rates, comparable to wired networks, but can cover only smaller areas, suitable for hot-spot applications in hotels and airports. The performance and flexibility of wireless data services would be dramatically improved if users could seamlessly roam across the two networks. In this paper, we address the problem of integration of these two classes of networks to offer such seamless connectivity. Specifically, we describe two possible integration approaches - namely tight integration and loose integration and advocate the latter as the preferred approach. Our realization of the loose integration approach consists of two components: a new network element called IOTA gateway deployed in 802.11 networks, and a new client software. The IOTA gateway is composed of several software modules, and with cooperation from the client software offers integrated 802.11/3G wireless data services that support seamless intertechnology mobility, Quality of Service (QoS) guarantees and multiprovider roaming agreements. We describe the design and implementation of the IOTA gateway and the client software in detail and present experimental performance results that validate our architectural approach.

To reduce Web access latencies, we propose a new paradigm for caching at the reference point of a document. If a document X is referred to from a document Y, information is cached at Y to reduce the latency of client accesses to X. We focus on two specific instances of this paradigm: caching IP addresses to avoid DNS lookups at clients, and caching information about documents to avoid setting up new connections. Avoiding DNS lookup saves over 4 seconds 10-12% of the time and avoiding connection setup saves 240 ms on the average. These ideas enable new services such as search engines that return IP addresses to speed up search sessions, and caching at regional information servers that goes beyond the capabilities of today's proxy caching.

Transmissionlinks often have different maximum packet sizes.Thus most network protocols allow large packets to be fragmented in order to be carried over a link with a small maximum packet size.The fragments are then reassembled either at the next hop or at the destination to recreate the original packet.However, both the old and the new versions of the Internet Protocol discourage fragmentation and reassembly.This is because the loss of a fragment can lead to the loss of a packet, and because reassembly implementations were perceived to be inefficient.In this paper, we reconsider the underlying principles of fragmentation and reassembly and introduce:(1) a more discriminating and general form of reassembly that allows reassembly to be done at any point in the network(2) a scheme to reduce the degradation in performance caused when fragments are lost and, (3) an efficient reassembly algorithm based on an expected case optimization that can process a fragment in 34 instructions.We use the Internet protocol suite to describe and evaluate specific modifications.We show that we can considerably improve end-to-end (i.e., TCP) performance using our mechanisms by effectively increasing link packet sizes beyond the required minimum.Experiments over a two hop path show an improvement of 42% (in TCP throughput) using hop by hop reassembly across a 1500 byte link.

We describe an efficient fair queuing scheme, leap forward virtual clock, that provides end-to-end delay bounds similar to weighted fair queuing (WFQ), along with throughput fairness. Our scheme can be implemented with a worst-case time O(loglogN) per packet (inclusive of sorting costs), which improves upon all previously known schemes that guarantee delay and throughput fairness similar to WFQ. Interestingly, both the classical virtual clock and the self-clocked fair queuing schemes can be thought of as special cases of our scheme, by setting the leap forward parameter appropriately.

No abstract available.

In high speed networks, packet processing is relatively expensive while bandwidth is cheap. Thus, it pays to add information to packet headers to make packet processing easier. While this is an old idea, we describe several specific new mechanisms based on this principle. We describe a new technique, source hashing, which can provide O(1) lookup costs at the data link, routing, and transport layers. Source hashing is especially powerful when combined with the old idea of a flow identifier (flow ID); the flow ID allows packet processing information to be cached and source hashing allows efficient cache lookups. Unlike virtual circuit identifiers (VCIs), source hashing does not require a round-trip delay for set up. In an experiment with the BSD packet filter implementation, we found that adding a flow ID and a source hash improved packet processing costs by a factor of seven. We also found a 45% improvement when we conducted a similar experiment with IP packet forwarding. We also describe two other new techniques: threaded indices, which allows fast VCI-like lookups for datagram protocols like IP; and a data manipulation layer (DML), which compiles out all the information needed for integrated layer processing (ILP) and scheduling into an easily accessible portion of each packet.

In high speed networks, packet processing is relatively expensive while bandwidth is cheap. Thus it pays to add information to packet headers to make packet processing easier. While this is an old idea, we describe several specific new mechanisms based on this principle. We describe a new technique, source hashing, which can provide O(1) lookup costs at the Data Link, Routing, and Transport layers. Source hashing is especially powerful when combined with the old idea of a flow ID; the flow identifier allows packet processing information to be cached, and source hashing allows efficient cache lookups. Unlike Virtual Circuit Identifiers (VCIs), source hashing does not require a round trip delay for set up. In an experiment with the BSD Packet Filter implementation, we found that adding a flow ID and a source hash improved packet processing costs by a factor of 7. We also found a 45% improvement when we conducted a similar experiment with IP packet forwarding. We also describe two other new techniques: threaded indices, which allows fast VCI-like lookups for datagram protocols like IP; and a Data Manipulation Layer, which compiles out all the information needed for Integrated Layer Processing into an easily accessible portion of each packet.