13323849
On the Extreme Parallelism Inside Next-Generation Network Processors
Next-generation high-end network processors (NP) must address demands from both diversified applications and ever-increasing traffic pressure. One major challenge is to design an extraordinary scalable architecture. In this paper, it is argued that such an objective can only be sufficed by introducing highly paralleled structure, namely the paralleled processing-engine cluster (PPC). We demonstrate this point from the trade-off among aspects such as performance, programmability and flexibility. However, PPC natively suffers from several critical issues on load-balancing, intra-flow packet ordering and memory contention. After investigating several existing approaches, we present novel solutions for each issue according to the balance between performance and coast. Through intensive analysis and comprehensive simulations, it is shown that the shortest queue first scheduling with class-based prediction (SQF-C) performs nearly optimally, while the hardware based per-flow ordering mechanism resolves packet out-of-order independently with the load-balancing issue, inducting little throughput degradation. Implementing the unified solution, it is capable to design a PPC supporting up to OC-768c line rate. Real implementation is also carried out in our THNPU-1 prototype to verify the conclusions.
17725194
SPF: to improve the performance of packet-mode scheduling
Recent researches present that packet-mode scheduling may provide overall performance advantages over cell-mode scheduling in input queueing switches. But one significant drawback of existing packet-mode schedulers is that they tend to result in longer waiting time of short packets, whose delay is critical to the performance of IP networks. To mitigate the problem, this paper proposes a simple but effective packet-mode scheduling algorithm called Short Packets First (SPF), studies the corresponding buffering architecture, and evaluates the performance on throughput and packet delay. SPF achieves 100% throughput under an accurate Internet traffic model. Theoretical analysis proves that SPF can reduce the average packet waiting time of short packets as well as overall packets, under the condition of uniform Poisson arrival process and low to medium offered load. Furthermore, extended simulation studies show that SPF is superior to general packet-mode and cell-mode scheduling, especially under heavy offered load.
5800626
Hybrid Cache Architecture for High Speed Packet Processing
The exposed memory hierarchies employed in many network processors (NPs) are expensive and hard to be effectively utilized. On the other hand, conventional cache cannot be directly incorporated into NP either because of its low efficiency in locality exploitation for network applications. In this paper, a novel memory hierarchy component, called split control cache, is presented. The proposed scheme employs two independent low latency memory stores to temporarily hold the flow-based and application-relevant information, exploiting the different locality behaviors exhibited by these two types of data. Data movement is manipulated by specially designed hardware to relieve the programmers from details of memory management. Performance evaluation shows that this component can achieve a hit rate of over 90% with only 16 KB of memories in route lookup under link rate of OC-3c and provide enough flexibility for the implementation of most network applications.
7704531
A TCAM-based distributed parallel IP lookup scheme and performance analysis
Using ternary content addressable memory (TCAM) for high-speed IP address lookup has been gaining popularity due to its deterministic high performance. However, restricted by the slow improvement of memory accessing speed, the route lookup engines for next-generation terabit routers demand exploiting parallelism among multiple TCAM chips. Traditional parallel methods always incur excessive redundancy and high power consumption. We propose in this paper an original TCAM-based IP lookup scheme that achieves both ultra-high lookup throughput and optimal utilization of the memory while being power-efficient. In our multi-chip scheme, we devise a load-balanced TCAM table construction algorithm together with an adaptive load balancing mechanism. The power efficiency is well controlled by decreasing the number of TCAM entries triggered in each lookup operation. Using four 133 MHz TCAM chips and given 25% more TCAM entries than the original route table, the proposed scheme achieves a lookup throughput of up to 533 MPPS while remains simple for ASIC implementation
5712150
Preemptive Packet-Mode Scheduling to Improve TCP Performance
Recent Internet traffic measurements show that 60% of the total packets are short packets, which include TCP acknowledgment and control segments. These short packets make a great impact on the performance of TCP. Unfortunately, short packets suffer from large delay due to serving long data packets in switches running in the packet mode, i.e. a packet is switched in its entirety. To optimize TCP performance, we apply a cross-layer approach to the design of switching architectures and scheduling algorithms. Specifically, we propose a preemptive packet-mode scheduling architecture and an algorithm called preemptive short packets first (P-SPF). Analysis and simulation results demonstrate that compared to existing packet-mode schedulers, P-SPF significantly reduces the waiting time for short packets while achieving a high overall throughput when the traffic load is heavy. Moreover, with a relatively low speedup, P-SPF performs better than existing packet-mode schedulers under any traffic load.
1001399
DS-PPS: A Practical Framework to Guarantee Differentiated QoS in Terabit Routers with Parallel Packet Switch
Parallel Packet Switch (PPS) is used intensively in today's terabit router to construct the switching fabric. Basic PPS equally deals with all of the traffic in order to achieve uniform load-balancing and high throughput, but it fails to support differentiated QoS. With the recent blooming of delay- sensitive Internet traffic, such as the peer-to-peer live streaming and IPTV, differentiated QoS is becoming an urgent demand. In this paper, we propose a novel and practical framework, the Differentiated Service Parallel Packet Switch (DS-PPS), which supports three fundamental QoS features: guaranteed-delay (GD), guaranteed-bandwidth (GB) and best-effort (BE). By adaptively adjusting the number of switching planes offered to each QoS class, DS-PPS precisely controls the delay bounds of GD traffic and the drop precedence of GB traffic. We evaluate DS-PPS by extensive theoretical analyses and comprehensive simulations. Experimental results on a prototype implementation of the framework show that DS-PPS outperforms the basic PPS in three main aspects. First, the average delay of TCP short packet under full load is reduced by more than 94%. Second, the average delay of real-time traffic under full load is reduced by more than 82%. And third, the GB traffic of low drop precedence is guaranteed of nearly three times the throughput of high drop precedence at the hotspots. Significantly, our proposed DS-PPS framework is universal and scalable to support various kinds of emerging QoS-sensitive applications in multi-service terabit routers without any extra overhead.
2578283
On the efficiency of fluid simulation of networks
Performance evaluation of computer networks through tratitional packet-level simulation is becoming increasingly difficult as networks grow in size along different dimensions. Due to its higher level of abstraction, fluid simulation is a promising approach for evaluating large-scale network models. In this paper we focus on evaluating and comparing the computaional effort required for fluid-and packet-level simulation. To measure the computaional effort required by a simulation approach, we introduce the concept of "simulation event rate", a measure that is both analytically tractable and adequate. We identify the fundamental factors that contribute to the simulation event rate in fluid- and packet-level simulations and provide an analytical characterization of the simulation event rate for specific network models. Among such factors, we identify the "ripple effect" as a significant contributor to the computational effort required by fluid simulation. We also show that the parameter space of a given network model can be divided into different regions where one simulation technique is more efficient than the other. In particular, we consider a realistic large-scale network and demonstrate how the computational effort depends on simulation parameters. Finally, we show that flow aggregation can effectively reduce the impact of the ripple effect and that the ripple effect has less impact when simulating the WFQ scheduling policy.
2853015
On the capacity of hybrid wireless networks
This paper involves the study of the throughput capacity of hybrid wireless networks. A hybrid network is formed by placing a sparse network of base stations in an ad hoc network. These base stations are assumed to be connected by a high-bandwidth wired network and act as relays for wireless nodes. They are not data sources nor data receivers. Hybrid networks present a tradeoff between traditional cellular networks and pure ad hoc networks in that data may be forwarded in a multihop fashion or through the infrastructure. It has been shown that the capacity of a random ad hoc network does not scale well with the number of nodes in the system. In this work, we consider two different routing strategies and study the scaling behavior of the throughput capacity of a hybrid network. Analytical expressions of the throughput capacity are obtained. For a hybrid network of n nodes and m base stations, the results show that if m grows asymptotically slower than √n, the benefit of adding base stations on capacity is insignificant. However, if m grows faster than √n, the throughput capacity increases linearly with the number of base stations, providing an effective improvement over a pure ad hoc network. Therefore, in order to achieve nonnegligible capacity gain, the investment in the wired infrastructure should be high enough.
8364982
Supporting Complex Multi-Dimensional Queries in P2P Systems
More and more applications require peer-to-peer (P2P) systems to support complex queries over multi-dimensional data. For example, a P2P auction network for real estate frequently needs to answer queries such as "select five available buildings closest to the airport". Such queries are not efficiently supported in current P2P systems. Towards an efficient and scalable P2P system capable of processing complex multi-dimensional queries, the authors first proposed a comprehensive framework for sharing, indexing, and querying multi-dimensional data, where (i) peers with more computational power coordinate indexing and query processing, and (ii) other peers participate in part of the computation in order to achieve scalability and load-balance. Based on this framework, Network-R-tree (NR-tree), a P2P adaptation of the dominant spatial index - R*-tree was proposed. NR-tree, indexing spatial data at clustered peers, is capable of processing complex queries such as range queries and k-nearest neighbor queries. The authors proposed query processing algorithms for range and k-nearest neighbor queries and experimentally prove the effectiveness of proposed techniques with real data
1727263
A study of networks simulation efficiency: fluid simulation vs. packet-level simulation
Network performance evaluation through traditional packet-level simulation is becoming increasingly difficult as today's networks grow in scale along many dimensions. As a consequence, fluid simulation has been proposed to cope with the size and complexity of such systems. This study focuses on analyzing and comparing the relative efficiencies of fluid simulation and packet-level simulation for several network scenarios. We use the "simulation event" rate to measure the computational effort of the simulators and show that this measure is both adequate and accurate. For some scenarios, we derive analytical results for the simulation event rate and identify the major factors that contribute to the simulation event rate. Among these factors, the "ripple effect" is very important since it can significantly increase the fluid simulation event rate. For a tandem queueing system, we identify the boundary condition to establish regions where one simulation paradigm is more efficient than the other. Flow aggregation is considered as a technique to reduce the impact of the "ripple effect" in fluid simulation. We also show that WFQ scheduling discipline can limit the "ripple effect", making fluid simulation particularly well suited for WFQ models. Our results show that tradeoffs between parameters of a network model determines the most efficient simulation approach.
7867063
D-CAPE: distributed and self-tuned continuous query processing
Efficient continuous query processing is critical for many applications, including monitoring remote sensors network traffic management, and online transaction processing. To overcome resource limitations and achieve real-time responsiveness, continuous query systems research focuses on issues such as punctuation-driven operator-state purging [4], load shedding, operator scheduling [7] and plan optimization and on-line migration [9]. However, when real-time yet accurate results are critical such as in stock market analysis, then there is a limitation to what any of the above optimization techniques can accomplish. Hence, distributed processing must be applied to support required scalability. It has been already proven in traditional database systems [3] that distributed processing results in high scale-up and speed-up capabilities due to aggregated resources. The design of a distributed continuous query system is characterized by an extra complexity, considered in the design of our D-Cape engine. In such a system, data streams may be infinite and initial cost statistics about the data streams are typically unknown. Moreover, cost statistics continue to change over time. Our research on distributed stream processing addresses two critical questions: (1) How to initially distribute query plans given little or possibly no cost information, and (2) How to efficiently adapt the query distribution corresponding to runtime environmental changes. Even though research is now under way in designing distributed continuous query systems [2], [1], results to date, as far as we know, are based on simulations. Our work offers empirical results of distributed continuous query processing using an actual software system [5], [6]. D-Cape, a distributed continuous query processing architecture, employs stream query engines over a cluster of shared-nothing processors. We employ a dedicated distribution manager to manage