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.
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.
46229467
Packet-Mode Priority Scheduling for Terabit Core Routers
Existing packet-mode schedulers will result in long waiting time for short control packets in IP networks. To overcome this problem, this paper proposes a packet-mode practical scheduling algorithm called short-packets-first (SPF). With uniform Poisson arrival process and low to medium offered load, we prove that SPF can reduce the average packet waiting time for overall packets by greatly lowering the average packet waiting time for short packets. Moreover, simulations under a real traffic model demonstrate that SPF performs very well compared with other packet-mode and cell-mode scheduling algorithms, especially for short packets under heavy offered load..
3063801
Iteration-Shared Scheduling Algorithms Abolishing the Departure-Time-Compatible Graph in Switch-Memory-Switch Switches
Switch-Memory-Switch (SMS) architecture exhibits an excellent performance due to its emulating the Output Queueing structure. However, in order to achieve the maximal matching, the first stage scheduling operates at a huge computational complexity, which blocks the SMS from practical implementation. In order to put SMS into more effective industrial applications, especially in super-large size switches/routers with multi-services environment, two parallel iterative scheduling algorithms, named IS-RRM and AIS-RRM respectively, are proposed in this paper. The algorithms abolish totally the traditional departure-time-compatible (DTC) graph, and by using iteration-sharing technology, greatly reduce the required iteration number in each time slot. Using a discrete-time Markov chain to model the AIS-RRM algorithm, we obtain its upper bound of cell loss rate. Meanwhile, experimental and theoretical results show that so long as the number of shared memories is twice the switch size, AIS-RRM algorithm can achieve a cell loss rate of 10 when the input buffer size is 15 and the iteration number of each time slot is 6, despite the arrival traffic pattern and the switch size. Furthermore, the iteration number required in each time slot can be further decreased by increasing the input buffer size.
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.
3143012
TCAM-based distributed parallel packet classification algorithm with range-matching solution
Packet classification (PC) has been a critical data path function for many emerging networking applications. An interesting approach is the use of TCAM to achieve deterministic, high speed PC However, apart from high cost and power consumption, due to slow growing clock rate for memory technology in general, PC based on the traditional single TCAM solution has difficulty to keep up with fast growing line rates. Moreover, the TCAM storage efficiency is largely affected by the need to support rules with ranges, or range matching. In this paper, a distributed TCAM scheme that exploits chip-level-parallelism is proposed to greatly improve the PC throughput. This scheme seamlessly integrates with a range encoding scheme, which not only solves the range matching problem but also ensures a balanced high throughput performance. Using commercially available TCAM chips, the proposed scheme achieves PC performance of more than 100 million packets per second (Mpps), matching OC768 (40 Gbps) line rate.
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.
14440312
Fluid Simulation of Large Scale Networks: Issues and Tradeoffs
Traditional discrete-event packet-level approaches to simulating computer networks become computationally infeasible as the number of network nodes or their complexity increases. An alternative approach, in which packet-level traffic sources are replaced by fluid sources, has been proposed to address this challenge. In this paper we compare the amount of computational effort needed to simulate a network using a packet-level approach versus a fluid-based approach. We quantitatively characterize the amount of computational effort needed by each approach using the notion of a simulation’s event rate, and derive expressions for the event rate of a packet and fluid flow at both the input and output sides of a queue. We show that fluid simulation can require less computational effort for simple networks. However, as the network size and complexity grow, the so-called ”ripple effect” can result in fluid simulations becoming more expensive than their packet-level counterparts. This suggests that time-driven (approximate) fluid simulation techniques may be needed to efficiently simulate large scale networks.
11333656
Efficient decoupling capacitor planning via convex programming methods
Achieving P/G supply signal integrity is crucial to success of nanometer VLSI designs. Existing P/G network optimization techniques are dominated by sensitivity based approaches. In this paper, we propose two novel convex programming based approaches for decoupling capacitor insertion in a P/G network, i.e., a semidefinite program and a linear program, which are global optimizations with theoretically guaranteed supply voltage degradation bounds. We also propose a scalability improvement scheme which enables us to apply the proposed convex programs to industry designs. We present a simple illustrative example and experimental results on an industry design, which show that the proposed semidefinite program guarantees supply voltage degradation bound for all possible supply current sources, while the proposed linear program achieves the most accurate supply voltage degradation control for a given set of supply current sources.
10079260
The sum number and integral sum number of complete bipartite graphs
Let N denote the set of positive integers. The sum graph G + (S) of a 1nite subset S of N is the graph (S; E) with vertex set S and edge set E such that for u; v ∈ S; uv ∈ E if and only if u + v ∈ S. A graph G is called a sum graph if it is isomorphic to the sum graph G + (S) of some 1nite subset S of N . The sum number � (G) of a graph G is de1ned as the smallest nonnegative integer m for which G ∪ mK1 is a sum graph. Let Z be the set of all integers. By extending the set N to Z in the above de1nitions of sum graphs and sum numbers, Harary [3] introduced the corresponding notions of integral sum graphs and integral sum number of a graph. In this paper, we evaluate the value of the sum number and integral sum number of the complete bipartite graph Kr; s. While the former one corrects the result given in [4], the latter settles completely a problem proposed in [3]. c � 2001 Elsevier Science B.V. All rights reserved.
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.