Soft QoS provisioning using the token bank fair queuing scheduling algorithm

Future-generation wireless packet networks will support multimedia applications with diverse QoS requirements. Much of the research on scheduling algorithms has been focused on hard QoS provisioning of integrated services. Although these algorithms give hard delay bounds, their stringent requirements sacrifice the potential statistical multiplexing performance and flexibility of the packet-switched network. Furthermore, the complexities of the algorithms often make them impractical for wireless networks. There is a need to develop a packet scheduling scheme for wireless packet-switched networks that provides soft QoS guarantees for heterogeneous traffic, and is also simple to implement and manage. This article proposes token bank fair queuing (TBFQ), a soft scheduling algorithm that possesses these qualities. This algorithm is work-conserving and has a complexity of O(1). We focus on packet scheduling on a reservation-based TDMA/TDD wireless channel to service integrated real-time traffic. The TBFQ scheduling mechanism integrates the policing and servicing functions, and keeps track of the usage of each connection. We address the impact of TBFQ on mean packet delay, violation probability, and bandwidth utilization. We also demonstrate that due to its soft provisioning capabilities, the TBFQ performs rather well even when traffic conditions deviate from the established contracts.     

Revisiting the fair queuing paradigm for end-to-end congestion control

Today, the dominant paradigm for congestion control in the Internet is based on the notion of TCP friendliness. To be TCP-friendly, a source must behave in such a way as to achieve a bandwidth that is similar to the bandwidth obtained by a TCP flow that would observe the same round-trip time (RTT) and the same loss rate. However, with the success of the Internet comes the deployment of an increasing number of applications that do not use TCP as a transport protocol. These applications can often improve their own performance by not being TCP-friendly, which severely penalizes TCP flows. To design new applications to be TCP-friendly is often a difficult task. The idea of the fair queuing (FQ) paradigm as a means to improve congestion control was first introduced by Keshav (1991). While Keshav made a fundamental step toward a new paradigm for the design of congestion control protocols, he did not formalize his results so that his findings could be extended for the design of new congestion control protocols. We make this step and formally define the FQ paradigm as a paradigm for the design of new end-to-end congestion control protocols. This paradigm relies on FQ scheduling with per-flow scheduling and longest queue drop buffer management in each router. We assume only selfish and noncollaborative end users. Our main contribution is the formal statement of the congestion control problem as a whole, which enables us to demonstrate the validity of the FQ paradigm. We also demonstrate that the FQ paradigm does not adversely impact the throughput of TCP flows and explain how to apply the FQ paradigm for the design of new congestion control protocols. As a pragmatic validation of the FQ paradigm, we discuss a new multicast congestion control protocol called packet pair receiver-driven layered multicast (PLM).     

Hardware implementation of fair queuing algorithms for asynchronoustransfer mode networks

Providing quality-of-service guarantees in both cell- and packet-based networks requires the use of a scheduling algorithm in the switches and network interfaces. These algorithms need to be implemented in hardware in a high-speed switch. The authors present a number of approaches to implement scheduling algorithms in hardware. They begin by presenting a general methodology for the design of timestamp-based fair queuing algorithms that provide the same bounds on end-to-end delay and fairness as those of weighted fair queuing, yet have efficient hardware implementations. Based on this general methodology, the authors describe two specific algorithms, frame-based fair queuing and starting potential-based fair queuing, and discuss illustrative implementations in hardware. These algorithms may be used in both cell switches and packet switches with variable-size packets. A methodology for combining a traffic shaper with this class of fair queuing schedulers is also presented for use in network interface devices, such as an ATM segmentation and reassembly device     

Handover compensation scheme for weighted fair queuing in cellularpacket switched networks

The unbounded fairness problem of WFQ induced by handovers in cellular packet switched networks is investigated and a new strategy for guaranteed bounded fairness is proposed. The simulation results show that the proposed scheme maintains bounded fairness, while in WFQ an increase in unfairness from a handover is cumulative, allowing a new flow to monopolise a wireless link in proportion to the increase     

Efficient fair queueing algorithms for packet-switched networks

Although weighted fair queueing (WFQ) has been regarded as an ideal scheduling algorithm in terms of its combined delay bound and proportional fairness properties, its asymptotic time complexity increases linearly with the number of sessions serviced by the scheduler, thus limiting its use in high-speed networks. An algorithm that combines the delay and fairness bounds of WFQ with O(1) timestamp computations had remained elusive so far. In this paper we present two novel scheduling algorithms that have O(1) complexity for timestamp computations and provide the same bounds on end-to-end delay and buffer requirements as those of WFQ. The first algorithm, frame-based fair queueing (FFQ), uses a framing mechanism to periodically recalibrate a global variable tracking the progress of work in the system, limiting any short-term unfairness to within a frame period. The second algorithm, starting potential based fair queueing (SPFQ), performs the recalibration at packet boundaries, resulting in improved fairness while still maintaining the O(1) timestamp computations. Both algorithms are based on the general framework of rate-proportional servers (RPSs) introduced by Stiliadis and Varma (see ibid., vol.6, no.2, p.164-74, 1998). The algorithms may be used in both general packet networks with variable packet sizes and in asynchronous transfer mode (ATM) networks     

Tradeoffs between low complexity, low latency, and fairness with deficit round-robin schedulers

Deficit Round-Robin (DRR) is a scheduling algorithm devised for providing fair queueing in the presence of variable length packets. The main attractive feature of DRR is its simplicity of implementation: in fact, it can exhibit O(1) complexity, provided that specific allocation constraints are met. However, according to the original DRR implementation, meeting such constraints often implies tolerating high latency and poor fairness. In this paper, we first derive new and exact bounds for DRR latency and fairness. On the basis of these results, we then propose a novel implementation technique, called Active List Queue Method (Aliquem), which allows a remarkable gain in latency and fairness to be achieved, while still preserving O(1) complexity. We show that DRR achieves better performance metrics than those of other round-robin algorithms such as Pre-Order Deficit Round-Robin and Smoothed Round-Robin. We also show by simulation that the proposed implementation allows the average delay and the jitter to be reduced.     

Efficient generation of fair dice with few biased coins

Given a random variable X which takes n equiprobable values, we consider several algorithmic questions related to the classical problem of simulating the outcomes of X by using a limited number of biased coins     

Deficit round-robin scheduling for input-queued switches

We address the problem of fair scheduling of packets in Internet routers with input-queued switches. The goal is to ensure that packets of different flows leave a router in proportion to their reservations under heavy traffic. First, we examine the problem when fair queuing is applied only at output link of a router, and verify that this approach is ineffective. Second, we propose a flow-based iterative deficit-round-robin (iDRR) fair scheduling algorithm for the crossbar switch that supports fair bandwidth distribution among flows, and achieves asymptotically 100% throughput under uniform traffic. Since the flow-based algorithm is hard to implement in hardware, we finally propose a port-based version of iDRR (called iPDRR) and describe its hardware implementation.     

Design of packet-fair queuing schedulers using a RAM-basedsearching engine

The implementation of packet-fair queuing (PFQ) schedulers, which aim at approximating the generalized processor sharing (GPS) policy, is a central issue for providing multimedia services with various quality-of-service (QoS) requirements in packet-switching networks. In the PFQ scheduler, packets are usually time stamped with a value based on some algorithm and are transmitted with an increasing order of the time-stamp values. One of the most challenging issues is to search for the smallest time-stamp value among hundreds of thousands of sessions. In this paper, we propose a novel RAM-based searching engine (RSE) to speed up the searching process by using the concept of hierarchical searching with a tree data structure. The time for searching the smallest time stamp is independent of the number of sessions in the system and is only bounded by the memory accesses needed. The RSE can be implemented with commercial memory and field programmable gate array (FPGA) chips in a cost-effective manner. With the extension of the RSE, we propose a two-dimensional (2-D) RSE architecture to implement a general shaper-scheduler. Other challenging issues, such as time-stamp overflow and aging, are also addressed in the paper     

Scalable fair reliable multicast using active services

Scalability is of paramount importance in the design of reliable multicast transport protocols, and requires careful consideration of a number of problems such as feedback implosion, retransmission scoping, distributed loss recovery, and congestion control. In this article, we present a reliable multicast architecture that invokes active services at strategic locations inside the network to comprehensively address these challenges. Active services provide the ability to quickly and efficiently recover from loss at the point of loss. They also exploit the physical hierarchy for feedback aggregation and effective retransmission scoping with minimal router support. We present two protocols, one for packet loss recovery and another for congestion control, and describe an experimental testbed where these have been implemented. Analytical and experimental results are used to demonstrate that the active services architecture improves resource usage, reduces latency for loss recovery, and provides TCP-friendly congestion control     

Fixed-point analysis of a network of routers with persistent TCP/UDP flows and class-based weighted fair queuing

Fixed-point models have already been successfully used to analytically study networks consisting of persistent TCP flows only, or mixed TCP/UDP flows with a single queue per link and differentiated buffer management for these two types of flows. In the current study, we propose a nested fixed-point analytical method to obtain the throughput of persistent TCP and UDP flows in a network of routers supporting class-based weighted fair queuing allowing the use of separate queues for each class. In particular, we study the case of two classes where one of the classes uses drop-tail queue management and is intended for only UDP traffic. The other class targeting TCP, but also allowing UDP traffic for the purpose of generality, is assumed to employ active queue management. The effectiveness of the proposed analytical method is validated in terms of accuracy using ns-3 simulations and the required computational effort.     

Handoff ordering using signal prediction priority queuing inpersonal communication systems

Handoffs in a mobile cellular communications environment will become an increasingly important issue as cell sizes shrink to accommodate an increasingly large demand for services. A new handoff ordering method is proposed which can be used to provide rapid handovers with a smaller percentage of dropped calls than other methods. Signal prediction priority queuing (SPPQ) is a generic queuing method which can be adapted to almost any handover technique for the benefit of decreased dropped calls. In typical personal communication systems (PCSs) environment, it is shown that for realistic call-blocking probabilities (2%-6%), SPPQ leads to about 15% fewer dropped calls compared to first-in-first-out (FIFO) queuing. This benefit comes at the expense of a slight increase (<1%) in blocked call percentage. The proposed SPPQ scheme is also compared to a previously developed method called measurement-based priority scheme (MBPS), and, based on worst case scenarios, it is shown to outperform MBPS as well     

Achieving round-robin access in controller area networks

Because of their low implementation costs, optimum responsiveness, and widespread availability, controller area networks (CANS) are being used more and more today to support communications in real-time systems. However, under heavy traffic conditions the CAN access protocol may exhibit a quite unfair behavior, in particular, when the control applications require the same quality of service to be ensured to a number of different objects. In this paper, a new technique is proposed which is based on CAN and introduces few changes to the original protocol. Such a solution is able to ensure a very fair behavior-which resembles the one obtained in token-based networks-while maintaining, at the same time, the reduced access delays typical of CAN when operating in low traffic conditions. Furthermore, it preserves an optimum degree of compatibility with the existing devices and applications based on CAN.     

Novel round-robin tabu search algorithm for prostate cancer classification and diagnosis using multispectral imagery.

Quantitative cell imagery in cancer pathology has progressed greatly in the last 25 years. The application areas are mainly those in which the diagnosis is still critically reliant upon the analysis of biopsy samples, which remains the only conclusive method for making an accurate diagnosis of the disease. Biopsies are usually analyzed by a trained pathologist who, by analyzing the biopsies under a microscope, assesses the normality or malignancy of the samples submitted. Different grades of malignancy correspond to different structural patterns as well as to apparent textures. In the case of prostate cancer, four major groups have to be recognized: stroma, benign prostatic hyperplasia, prostatic intraepithelial neoplasia, and prostatic carcinoma. Recently, multispectral imagery has been used to solve this multiclass problem. Unlike conventional RGB color space, multispectral images allow the acquisition of a large number of spectral bands within the visible spectrum, resulting in a large feature vector size. For such a high dimensionality, pattern recognition techniques suffer from the well-known "curse-of-dimensionality" problem. This paper proposes a novel round-robin tabu search (RR-TS) algorithm to address the curse-of-dimensionality for this multiclass problem. The experiments have been carried out on a number of prostate cancer textured multispectral images, and the results obtained have been assessed and compared with previously reported works. The system achieved 98%-100% classification accuracy when testing on two datasets. It outperformed principal component/linear discriminant classifier (PCA-LDA), tabu search/nearest neighbor classifier (TS-1NN), and bagging/boosting with decision tree (C4.5) classifier.     

Efficient arithmetic using self-timing

Recent advances in VLSI technology have facilitated high levels of integration and the implementation of faster circuits on a chip. Most of the improvements in the performance of digital systems have been brought about by such faster technologies. However, these improvements in technology have brought along with them a host of other constraints. In the faster deep submicron technologies, the wire delays constitute a significant portion of the overall delay of the system and hence some of the advantages of faster technologies are lost. The high level of integration necessitates clock distribution schemes which minimize skew across the die. These result in area penalties and adversely affect the level of integration possible at the chip level. Hence, changes in the basic architecture of computing elements of a system, which when implemented in silicon introduces reduced interconnect delays and simpler clock distribution networks, will result in more effective performance improvements. The work presented here examines the implementation of the most basic element in any datapath-an adder. The adder, a carry elimination adder (CEA), uses self-timing at both the algorithmic and implementation levels and presents a minimal hardware high speed addition mechanism. The adder exploits the nature of the input operands dynamically, which results in its average case convergence time approaching that of the ubiquitous carry lookahead adder (CLA) and the hardware complexity of a carry ripple adder (CRA). Use of self-timing results in the elimination of a global clock and hence clock-skew     

Analytical model of round-robin scheduling for a geostationary satellite system

Round-robin scheduling is commonly employed in time-division multiple-access based medium access control protocols, to provide users with equitable access to a shared channel. The letter presents an analytical model to evaluate the mean end-to-end delay of packets traversing a geostationary satellite link with a round-robin free assignment scheduling strategy and Poisson source traffic. It is shown that the model can accurately predict the end-to-end delay performance of a round-robin scheduling satellite system.     

Captured-frame eligibility and round-robin matching for input-queued packet switches

A variety of matching schemes for input-queued (IQ) switches that deliver high throughput under traffic with uniform distributions has been proposed. However, there is a need of matching schemes that provide high throughput under several admissible traffic patterns, including those with nonuniform distributions, while keeping implementation complexity low. In this letter, first, we introduce the captured frame concept for matching schemes in IQ switches. Second, we propose a round-robin based matching scheme, uFORM, which uses the proposed concept for cell matching eligibility. We show via simulation that our matching scheme delivers high throughput under several nonuniform traffic patterns, and retains the high performance under uniform traffic that round-robin matching schemes are known to offer.     

Fair scheduling with tunable latency: a round-robin approach

Weighted fair queueing (WFQ)-based packet scheduling schemes require processing at line speeds for tag computation and tag sorting. This requirement presents a bottleneck for their implementation at high transmission speeds. We propose an alternative and lower complexity approach to packet scheduling, based on modifications of the classical round-robin scheduler. Contrary to conventional belief, we show that appropriate modifications of the weighted round-robin (WRR) service discipline can, in fact, provide tight fairness properties and efficient delay guarantees to multiple sessions. Two such modifications are described: 1) list-based round robin, in which the server visits different sessions according to a precomputed list which is designed to obtain the desirable scheduling properties; 2) multiclass round robin, a version of hierarchical round robin with controls designed for good scheduling properties. The schemes considered are compared with well-known WFQ schemes and with deficit round robin (a credit-based WRR), on the basis of desirable properties such as bandwidth guarantees, fairness in excess bandwidth sharing, worst-case fairness, and efficiency of latency (delay guarantee) tuning. The scheduling schemes proposed and analyzed here operate with fixed packet sizes, and hence can be used in applications such as cell scheduling in ATM networks, time-slot scheduling on wireless links as in GPRS air interface, etc. A credit-based extension of the proposed schemes to handle variable packet sizes is also possible.     

Unreliable queuing with repeated orders

The study of queuing models with repeated orders is motivated by new developments in telecommunication technology as the use of “repeat-last-number”, “auto-repeat”, “ring-back-when- free” and other facilities [31,38,40]. In this paper we focalise our attention in an important aspect: the influence of the reliability of the communication line on the distribution of the number A(t) of customers in the system.First we give a short review of studies in this area. Next, we consider a version of the unreliable M/G/1/1 queue with repeated orders. The distribution of the non-markovian jump-process A(t), t≥0 is studed by an adequate “markovization”. We obtain a generalization of the Pollaczek-Khintchin-Alexandrov formula     

Two-dimensional round-robin schedulers for packet switches withmultiple input queues

Presents a new scheduler, the two-dimensional round-robin (2DRR) scheduler, that provides high throughput and fair access in a packet switch that uses multiple input queues. We consider an architecture in which each input port maintains a separate queue for each output. In an N×N switch, our scheduler determines which of the queues in the total of N² input queues are served during each time slot. We demonstrate the fairness properties of the 2DRR scheduler and compare its performance with that of the input and output queueing configurations, showing that our scheme achieves the same saturation throughput as output queueing. The 2DRR scheduler can be implemented using simple logic components, thereby allowing a very high-speed implementation