We introduce split-level I/O scheduling, a new framework that splits I/O scheduling logic across handlers at three layers of the storage stack: block, system call, and page cache. We demonstrate that traditional block-level I/O schedulers are unable to meet throughput, latency, and isolation goals. By utilizing the split-level framework, we build a variety of novel schedulers to readily achieve these goals: our Actually Fair Queuing scheduler reduces priority-misallocation by 28x; our Split-Deadline scheduler reduces tail latencies by 4x; our Split-Token scheduler reduces sensitivity to interference by 6x. We show that the framework is general and operates correctly with disparate file systems (ext4 and XFS). Finally, we demonstrate that split-level scheduling serves as a useful foundation for databases (SQLite and PostgreSQL), hypervisors (QEMU), and distributed file systems (HDFS), delivering improved isolation and performance in these important application scenarios.

Providing quality of service (QoS) is a critical issue in the current Internet. Recently, many distributed bandwidth broker architectures have been proposed for scalable QoS provision. One important task of bandwidth brokers is admission control, which decides whether a new data flow can be admitted without violating the QoS requirements of other existing data flows. In distributed bandwidth broker architectures, an admission control request needs to be processed by all bandwidth brokers on its path. Thus it is important for bandwidth brokers to schedule the processing of requests properly so that as many as possible requests can be processed within setup latency bounds. Most existing end-to-end delay-guarantee scheduling schemes depend on bandwidth reservation, traffic characterization, or priorities, which are not applicable to the scheduling of control plane requests. In this paper, we propose a new multi-hop coordinated scheduling algorithm P-EDF to improve the throughput of the admission control requests that are processed within setup latency bounds in distributed bandwidth broker architectures. Simulation results show that the P-EDF scheduling algorithm can achieve 20/spl sim/30% higher throughput in request processing than other existing scheduling algorithms in distributed bandwidth broker architectures.

On-line traffic, including conversational calls, videoconference calls, and live video, is becoming an important type of traffic in the Internet. The traffic traces of on-line traffic are not pre-recorded, which means little information on the on-line traffic is known in advance. Hence, on-line traffic is hard to characterize by existing traffic models, such as D-BIND. In order to anticipate and capture the burstiness property of on-line traffic, we introduce a new confidence-level-based statistical bounding interval-length dependent (S-BIND) traffic model and a statistical admission control algorithm, based on the S-BIND traffic model: the GammaH-BIND algorithm. Our simulation results show that by using the S-BIND traffic model as inputs, the GammaH-BIND algorithm can achieve the maximum valid network utilization for both low-bursty and high-bursty on-line traffic, which is 50%/spl sim/70% higher than the achievable network utilization under the D-BIND traffic model.

QoS architectures define how routers process packets to ensure that QoS service guarantees are enforced. Previous QoS architectures such as integrated services (IntServ), differentiated services (DiffServ), and dynamic packet state (DPS) share one common property that the packet structure and the function of the routers are closely connected. We propose to decouple the connection between packet structure and router functions. The packets should carry as much information as possible, while the routers should process the packets as detailed as possible until the load prohibits. We call such novel QoS architecture adaptive services (A-Serv). A-Serv utilizes a load adaptive router to provide QoS to data flows, while the treatment of each data flow is not predefined but based on the load of the router. A-Serv overcomes the scalability problem of IntServ, provides better service guarantees to individual data flows than DiffServ and can be deployed gradually. Our simulation results show that compared to the DiffServ architecture, A-Serv can provide differentiated services to the data flows in the same DiffServ class and provide guaranteed QoS to part of the data flows. Furthermore, A-Serv provides better protection to the data flows than DiffServ when malicious data flows exist.

In this paper, we present a high-performance implementation for the search function of a graph-based packet classification algorithm, used by networking applications in Internet routers, on the Intel IXP1200 network processor. The implementation uses optimal consolidation of memory reads to reduce the number of expensive SRAM accesses. Also, the implementation inserts instructions after SRAM accesses to hide the memory access latencies and improve processor utilization. Experimental results show the performance of the implemented search function on the IXP1200 using five microengines at 166 MHz can be as high as 1.18 Msps (million searches per second), which satisfies the requirements of packet rates from OC-3 or fast Ethernet and up to OC-12 or Gigabit Ethernet. The methods presented here can also be adapted to other network processors with similar architectures.

Packet classification is necessary for flow-based network services in Internet routers, such as NAPT, IPsec, ACL, etc. The range-based packet classification function maps input packets to the highest-priority matching rule in a given rule set specified by ranges (P. Gupta and N. McKeown, August 1999, March-April 2001). For instance, multi-field range-based packet classification maps IP packets to security policy rules in an IPsec gateway. The FIS trees based packet classification algorithm has been proposed as a software implementation option of this function. In this paper, we present a novel disjoint graph based algorithm for multi-field range-based packet classification. The novel algorithm constructs a disjoint graph using elementary interval trees and disjoint interval trees for a given rule set, where only a single path traversal is required during a search to classify a packet. Experimental results show that the disjoint graph based packet classification algorithm significantly outperforms the FIS trees based solution. In a network processor implementation with an input rule set of 700 rules, the disjoint graph based packet classification algorithm requires only 45% of the search time, 69% of the data structure buildup time, and 47% of the memory storage of the FIS trees based solution.

The Rivest, Shamir and Adleman (1978) RSA algorithmis a popular cryptography algorithm widely used in signing and encrypting operations for security systems. Generally, the software implementations of the RSA algorithm are based on 2-prime RSA. The multi-prime RSA has been proposed to speed up RSA implementations. Both 2-prime and multi-prime implementations require squaring reduction and multiplication reduction of multi-precision integers. The Montgomery (1985) reduction algorithm is the most efficient for the squaring and multiplication reductions. We present a new method to implement the Montgomery squaring reduction, which speeds up squaring reduction by 10-15% for various key sizes. Furthermore, a multi-prime 1024-bit RSA signing operation is implemented on the TI TMS320C6201 DSP processor with the new reduction method. As a result, the signing operation can be finished within 6 ms, which is about twice faster than the RSA implementation of Itoh, Takenaka, Torii, Temma and Kurihara (see Proc. of CHES'99, p.61-71, 1999) on the same DSP platform.

RSA is a popular cryptography algorithm widely used in signing and encrypting operations for security systems. Generally, the software implementations of RSA algorithm are based on 2-prime RSA. Recently multi-prime RSA has been proposed to speed up RSA implementations. Both 2-prime and multi-prime implementations require squaring reduction and multiplication reduction of multi-precision integers. Montgomery reduction algorithm is the most efficient way to do squaring and multiplication reductions. In this paper, we present a new method to implement the Montgomery squaring reduction, which speeds up squaring reduction by 10-15% for various key sizes. Furthermore, a multi-prime 1024-bit RSA signing operation is implemented on Tl TMS320C6201 DSP processor with the new reduction method. As the result, signing operation can be finished within 6ms, which is about twice faster than the RSA implementation in [K. Itoh et al., 1999] on the same DSP platform.