Hardware implementation study of several new egress link scheduling algorithms

The provision of Quality of Service (QoS) in interconnection networks is required for new multimedia and time-sensitive applications, which are very important for recent utility computing data centers (UCDCs) using high performance networks. These interconnection networks support switch-based principles and establish high demands in terms of bandwidth, time-delay, and delivery over short distances. A key component for networks with QoS support is the egress link scheduling algorithm. Apart from providing a good performance in terms of, for example, good end-to-end delay (also called latency) and fair bandwidth allocation, an ideal scheduling algorithm implemented in a high-performance network with QoS support should satisfy another important property which is to have a low computational and implementation complexity. In this paper, we propose specific implementations (taking into account the characteristics of current high performance networks) of several fair-queuing scheduling algorithms and compare their complexity in terms of silicon area and computation delay. In order to carry out this comparison, we have devised our own hardware comparison methodology. Following this methodology, we have performed our own hardware implementation for the different schedulers. We have modeled the schedulers using the Handel-C language and employed the DK design suite tool from Celoxica in order to obtain hardware estimates on silicon area and arbitration time.     

A Framework to Provide Quality of Service over Advanced Switching

Advanced switching (AS) is a network technology that expands the capabilities of PCI-express adding new features like peer-to-peer communication. Together, PCI express and AS have the potential for building the next generation interconnects. Furthermore, the provision of quality of service (QoS) in computing and communication environments is currently the focus of much discussion and research in industry and academia. In this paper we propose a framework to provide QoS based on bandwidth, latency, and jitter over AS employing the mechanisms provided by AS. We also present several implementations for the output scheduling mechanism. Finally, we evaluate our proposals by simulation, comparing the performance of the schedulers that we propose and their implementation complexity.     

Delivering relative differentiated services in future high-speed networks using hierarchical dynamic deficit round robin

With the increasing deployment of real-time audio/video services over the Internet, provision of quality of service (QoS) has attracted much attention. When the line rate of future networks upgrades to multi-terabits per second, if routers/switches intend to deliver differentiated services through packet scheduling, the reduction of computational overhead and elimination of bottleneck resulting from memory latency will both become important factors. In addition, the decrease of average queueing delay and provision of small delays for short packets are two further critical factors influencing the delivery of better QoS for real-time applications. The advanced waiting time priority (AWTP) is a timestamp-based packet scheduler which is enhanced from the well-known WTP. Although AWTP considers the effect of packet size, the latency resulting from timestamp access and a great quantity of computational overhead may result in bottlenecks for AWTP being deployed over high-speed links. Many existing schedulers have the same problems. We propose a multi-level hierarchical dynamic deficit round-robin (MLHDDRR) scheduling scheme which is enhanced from the existing dynamic deficit round-robin scheduler. The new scheme can resolve these issues and efficiently provide relative differentiated services under a variety of load conditions. Besides, MLHDDRR can also protect the highest priority traffic from significant performance degradation due to bursts of low-priority traffic. We compare the performance of AWTP with the proposed scheme. Extensive simulation results and complexity analysis are presented to illustrate the effectiveness and efficiency of MLHDDRR.     

Multicast support in multi-chip centralized schedulers in Input Queued switches

IQ switches store packets at input ports to avoid the memory speedup required by OQ switches. However, packet schedulers are needed to determine an I/O (input/output) interconnection pattern that avoids conflicts among packets at output ports. Today, centralized, single-chip, scheduler implementation are largely dominant. In the near future, the multi-chip scheduler implementation will be needed to reduce the hardware scheduler complexity in very large, high-speed, switches. However, the multi-chip implementation implies introducing a non-negligible delay among input and output selectors used to determine the I/O interconnection pattern at each time slot. This delay, mainly due to inter-chip latency, requires modifications to traditional scheduling algorithms, which normally rely on the hypothesis that information exchange among selectors can be performed with negligible delay. We propose a novel multicast scheduler, named IMRR, an extension of a previously proposed multicast scheduling algorithm named mRRM, making it suitable to a multi-chip implementation, and examine its performance by simulation.     

Quantum-Based Earliest Deadline First Scheduling for Multiservices

Latency-rate (LR) schedulers have shown their ability in providing fair and weighted sharing of bandwidth with an upper bound on delivery latency of packets while earliest departure first (EDF) schedulers have shown their ability in providing LR-decoupled service whereby the delivery latency of packets is not bounded by the reserved rate. However, EDF schedulers require traffic shapers to ensure flow protection. We propose quantum-based earliest deadline first scheduling (QEDF), a quantum-based scheduler that provides flow protection, throughput guarantee and delay bound guarantee for flows that require LR-coupled and LR-decoupled types of reservations. It classifies flows into time-critical (TC), jitter-sensitive (JS), and rate-based (RB) classes and uses a quality-of-service forwarding rule to determine the next packet to be serviced by the scheduler. It provides nonpreemptive priority service to TC queues. This allows LR-decoupled reservation for flows that have a low rate and intolerable delay. Packets from JS queues can be delayed by other packets if forwarding the latter will not result in the former missing its deadline. As a quantum-based scheduler, the QEDF scheduler provides throughput guarantees for RB queues. We present both analytical and simulation results of QEDF, whereby we evaluated QEDF in its deployment as a single-class as well as a multiservice scheduler     

TEMPEST: a new Test EnvironMent for Performance Evaluation of the Scheduling of packeTs

The packet scheduling problem has been deeply studied for lot of years by researchers in the computer science and telecommunications fields as an important solution that decides the order in which packets are sent over a link in order to provide QoS on a network. Recently, the packet scheduling has become again a challenging topic due to the massive use of wireless technologies (e.g. WiFi, LTE, 4G/5G) with which to provide high QoS guarantees is still an open problem. Unfortunately, it is difficult to compare different solutions and actually test them in order to select the most proper packet scheduler for each particular environment. In this paper we present TEMPEST, a new Test EnvironMent for Performance Evaluation of the Scheduling of packeTs, which is a novel tool able to help the research in the packet scheduling field. TEMPEST is able to measure the actual performance of a packet scheduler in several environments, both wired or wireless, like the execution time, QoS metrics and throughput, giving prompt feedback about the quality of the solution studied. The goal of this paper is to present in detail the current features of TEMPEST, showing how it is easy to add, configure, test and evaluate several scheduling solutions in multiple scenarios.     

A QoS-enhanced intelligent stochastic real-time packet scheduler for multimedia IP traffic

A re-configurable, QoS-enhanced intelligent stochastic real-time optimal fair packet scheduler, QUEST, for IP routers is proposed and investigated. The objective is to maximize the system QoS subject to the constraint that the processor utilization is kept at 100%. All past work on router schedulers for multimedia traffic were of earlier generation, in that they focused on maximizing utilization whereas being QoS-aware but without explicitly maximizing the QoS. Keeping utilization fixed at nearly 100%, QoS is dynamically maximized, thus moving to the next generation. QUEST’s other unique advantages are three-fold. First, it solves the challenging problem of starvation for low priority processes; second, it solves the major bottleneck of Earliest Deadline First scheduler’s failure at heavy traffic loads. Finally, QUEST offers the benefit of arbitrarily pre-programming the process utilization ratio. Three classes of multimedia IP traffic, namely, VoIP, IPTV and HTTP have been considered. Two most important QoS metrics, namely, packet loss rate (PLR) and mean waiting time, are addressed. All claims are supported by discrete event and Monte Carlo simulations. The proposed scheduler outperforms benchmark schedulers and offers 37% improvement in packet loss rate and 23% improvement in mean waiting time over the best competing current scheduler Accuracy-aware EDF. The proposed scheduler was validated in a test-bed platform of a NetFPGA® router and results were observed with Paessler® PRTG network monitor.

     

Incorporating packet semantics in scheduling of real-time multimedia streaming

In this work, we develop a novel packet scheduling algorithm that properly incorporates the semantics of a packet. We find that improvement in overall packet loss does not necessarily coincide with improvement in user perceivable QoS. The objective of this work is to develop a packet scheduling mechanism which can improve the user perceivable QoS. We do not focus on improving packet loss, delay, or burstiness. We develop a metric called, “Packet Significance,” that effectively quantifies the importance of a packet that properly incorporates the semantics of a packet from the perspective of compression. Packet significance elaborately incorporates inter-frame, intra-frame information dependency, and the transitive information dependency characteristics of modern compression schemes. We apply packet significance in scheduling the packet. In our context, packet scheduling consists of two technical ingredients: packet selection and interval selection. Under limited network bandwidth availability, it is desirable to transmit the subset of the packets rather than transmitting the entire set of packets. We use a greedy approach in selecting packets for transmission and use packet significance as the selection criteria. In determining the transmission interval of a packet, we incorporate the packet significance. Simulation based experiments with eight video clips were performed. We embed the decoding engine in our simulation software and examine the user perceivable QoS (PSNR). We compare the performance of the proposed algorithm with best effort scheduling scheme and one with simple QoS metric based scheduling scheme. Our Significance-Aware Scheduling scheme (SAPS) effectively incorporates the semantics of a packet and delivers best user perceivable QoS. SAPS can result in more packet loss or burstier traffic. Despite these limitations, SAPS successfully improves the overall user perceivable QoS.     

Two schedulers to provide delay proportion and reduce queueing delay simultaneously

The proportional delay differentiation model provides controllable and predictable delay differentiation, that is, the packet delay proportion between two classes of services is consistent on any measured timescale. Previous studies have focused on improving the accuracy of the achieved delay proportion between classes, and have not considered reducing the packet queueing delay, since these proposed scheduling algorithms are independent of the packet service time, such that the mean queueing delay is invariant, as specified by the conservation law. This paper proposes maximum WTP (MWTP) and variance WTP (VWTP) schedulers, modified from the waiting-time priority (WTP) algorithm which is an excellent scheduler for performing proportional delay differentiation. All of the proposed schedulers account for the packet transmission time. Simulation results indicate that when the link utilization is moderate, the two schedulers not only yield more accurate delay proportions than the WTP scheduler, regardless of whether the timescale is long or short, but also reduce the mean queueing delay. The effects of load distribution, packet size, and coefficient of variation (CoV) of packet sizes, on the performance of all schedulers are also investigated. Our proposed schedulers always outperform WTP.     

图书馆多媒体业务流的短时公平分组反馈调度方法

研究了一种新的基于短时公平的分组调度算法的问题. 基于短时公平性的分组反馈调度算法改进了WF2Q＋算法在短期内无法为新加入客户端提供公平服务的缺陷,增强了调度算法的适应性和公平性. 在本算法中,调度器中的各个客户端权值能够根据其获得的实际服务量状况在线调整,增强了系统的鲁棒性和自适应性,同时提高了系统实现短期公平性的能力,对各个客户端提供更为公平的服务质量（Quality of Service,QoS）.     

Cuttle：一种新的基于内容的通用调度器

随着互联网迅猛发展，研究Web请求的调度分配技术已成为国内外研究的热点。针对现有Web调度器存在着可扩展性差、系统开销大和无通用性诸多缺陷，设计和实现了一种新 的、通用的、可扩展性好的基于内容的通用调度器Cuttle。该系统在内核TCP／IP层实现，采用伪服务器、捎带技术、截获、伪装三次握手、Mix-LARD调度策略等技术。实验表明，Cuttle的可扩展性好，响应延迟小。     

Hardware design and implementation of packet fair queuing algorithms for the quality of service support in the high-speed internet

The increasing amount of real-time traffic carried over the Internet requires end-to-end quality of service (QoS) support. To this end, the QoS Schedulers, that are implemented in routers, assign the available bandwidth resources to packet flows according to their respective allocated rates. Packet Fair Queuing (PFQ) schedulers can provide fair service and low end-to-end delay bound to the traffic flows. However, they have higher implementation complexity compared to other algorithms, because of the requirements of tracking the system state, and searching for the packet to get service among all flows, that are queued at the outgoing interface. QoS scheduling is a data plane functionality, which requires hardware implementation for high speed router interfaces. The previous works on hardware implementation of PFQ schedulers are specific to certain algorithms, and they do not provide any results on real hardware platforms. In this paper, we present a general hardware design framework for PFQ schedulers, and apply this framework to the WF²Q+ PFQ algorithm to demonstrate its properties. We carry out the entire implementation of the WF²Q+ algorithm on an FPGA, and evaluate its performance with real traffic flows. In addition, we implement WFQ as a second PFQ algorithm to demonstrate the generality of the framework.     

适用于实时应用的网络服务自适应系统

随着网络带宽可用性的提高以及网络延迟的减少,如何在端主机上保证网络传输的服务质量(End-hostQoS)已经逐渐成为一个关键的问题。尤其是针对分布式实时应用的环境:媒体流服务器,视频会议以及VoIP((Voiceover Internet Protocol)是一种以IP电话为主,并推出相应的增值业务的技术应用)。End-hostQoS的实现需要操作系统的支持,比如提供网络层的系统调度和流量控制。笔者在这篇文章中提出的QoS自适应系统可以在最优使用系统资源的基础上提供per-flow或者per-service-class的差别服务。并且通过将EDF调度算法同PID控制理论相结合,保证系统的实时响应、适应网络波动,在服务器瞬间过载的情况下,保证网络服务质量的平稳过渡。     

On network CoProcessors for scalable, predictable media services

This paper presents the embedded realization and experimental evaluation of a media stream scheduler on network interface (NI) CoProcessor boards. When using media frames as scheduling units, the scheduler is able to operate in real-time on streams traversing the CoProcessor, resulting in its ability to stream video to remote clients at real-time rates. This paper presents a detailed evaluation of the effects of placing application or kernel-level functionality, like packet scheduling on NIs, rather than the host machines to which they are attached. The main benefits of such placement are: 1) that traffic is eliminated from the host bus and memory subsystem, thereby allowing increased host CPU utilization for other tasks, and 2) that NI-based scheduling is immune to host-CPU loading, unlike host-based media schedulers that are easily affected even by transient load conditions. An outcome of this work is a proposed cluster architecture for building scalable media servers by distributing schedulers and media stream producers across the multiple NIs used by a single server and by clustering a number of such servers using commodity network hardware and software.     

Cello: A Disk Scheduling Framework for Next Generation Operating Systems*

In this paper, we present the Cello disk scheduling framework for meeting the diverse service requirements of applications. Cello employs a two-level disk scheduling architecture, consisting of a class-independent scheduler and a set of class-specific schedulers. The two levels of the framework allocate disk bandwidth at two time-scales: the class-independent scheduler governs the coarse-grain allocation of bandwidth to application classes, while the class-specific schedulers control the fine-grain interleaving of requests. The two levels of the architecture separate application-independent mechanisms from application-specific scheduling policies, and thereby facilitate the co-existence of multiple class-specific schedulers. We demonstrate that Cello is suitable for next generation operating systems since: (i) it aligns the service provided with the application requirements, (ii) it protects application classes from one another, (iii) it is work-conserving and can adapt to changes in work-load, (iv) it minimizes the seek time and rotational latency overhead incurred during access, and (v) it is computationally efficient.     

Scheduling Threads for Low Space Requirement and Good Locality

The running time and memory requirement of a parallel program with dynamic, lightweight threads depends heavily on the underlying thread scheduler. In this paper we present a new asynchronous, space-efficient scheduling algorithm for shared memory machines that combines the low scheduling overheads and good locality of work stealing with the low space requirements of depth-first schedulers. For a nested-parallel program with depth D and serial space requirement S ₁ , we show that the expected space requirement is S ₁ + O(K⋅ p⋅ D) on p processors. Here, K is a user-adjustable runtime parameter, which provides a tradeoff between running time and space requirement. Our algorithm achieves good locality and low scheduling overheads by automatically increasing the granularity of the work scheduled on each processor. We have implemented the new scheduling algorithm in the context of a native, user-level implementation of Posix standard threads or Pthreads, and evaluated its performance using a set of C-based benchmarks that have dynamic or irregular parallelism. We compare the performance of our scheduler with that of two previous schedulers: the thread library's original scheduler (which uses a FIFO queue), and a provably space-efficient depth-first scheduler. At a fine thread granularity, our scheduler outperforms both these previous schedulers, but requires marginally more memory than the depth-first scheduler. We also present simulation results on synthetic benchmarks to compare our scheduler with space-efficient versions of both a work-stealing scheduler and a depth-first scheduler. The results indicate that unlike these previous approaches, the new algorithm covers a range of scheduling granularities and space requirements, and allows the user to trade the space requirement of a program with the scheduling granularity. Received June 11, 2000, and in revised form March 19, 2001, and in final form August 7, 2001. Online publication April 5, 2002.     

A formally verified application-level framework for real-time scheduling on POSIX real-time operating systems

We present a framework, called meta scheduler, for implementing real-time scheduling algorithms. The meta scheduler is a portable middleware layer component designed for implementations over POSIX-compliant operating systems. It accommodates pluggable real-time scheduling algorithms while offering the flexibility of platform independence - the singular underlying OS requirement is the now nearly ubiquitous POSIX compliance. The versatility of pluggable schedulers positions the meta scheduler for deployment in an interoperable heterogeneous real-time environment. We present the design of the meta scheduler and outline its implementation. Furthermore, we present a mechanized correctness verification using the UPPAAL model checker. Prototype implementation of the meta scheduler over QNX Neutrino real-time operating system demonstrates high performance and a small footprint.     

Application‐specific thread schedulers for distributed applications

This paper describes our work to improve the performance of distributed applications. We aim at certain application characteristics such as balancing load, allowing separately written applications to work better together, allowing a distributed application to adapt its behavior in more flexible ways, and so on. Our approach is to write application‐specific schedulers, which can access the global state of the application in making scheduling decisions. To achieve this goal, we extended our earlier work on CATAPULTS ( C reating A nd T esting AP plication‐specific U ser L evel T hread S chedulers), a domain‐specific language for creating and testing application‐specific user‐level thread schedulers, to distributed applications by adding ‘master schedulers’ for dealing with the distributed parts of applications. This paper presents our design of, experimentation with, and implementation of distributed CATAPULTS. This paper presents several realistic examples to measure the feasibility of this approach, specifically: a website application, an embedded application, and load balancing. Each example has a scheduling goal for which we developed a customized scheduler. We measured the performance with and without the customized scheduler. The customized scheduler for each example was fairly straightforward to develop and each achieved its scheduling goal. Copyright © 2011 John Wiley & Sons, Ltd.     

A genetic approach for downlink packet scheduling in HSDPA system

High speed downlink packet access (HSDPA) system currently under development in 3rd generation partnership project (3GPP) [1] employs number of parallel shared channels and adaptive modulation and coding scheme (MCS) to enable a high rate packet data transfer from base station (Node-B) to user equipment (UE). To decide how to share the available radio channel capacity amongst the active UEs, a packet scheduling and channel assignment algorithms are employed at Node B. Packet scheduling techniques such as max carrier to interference ratio (C/I) or round robin (RR) fails to take into account all the aspects of the quality of service (QoS) provisioning. In this paper, the fundamentals genetic algorithms and conventional wireless scheduling techniques are combined and the weaknesses of the existing known techniques are exploited to propose a novel hybrid genetic packet scheduler (HGPS) for the HSDPA system. A combination of random and intelligent diversity of population and comparative nature of the selection process of genetic engine contribute to its robustness. The proposed HGPS outperforms Max C/I packet scheduler in terms of total delivered throughput within low delay thresholds. Unlike conventional packet scheduling technique HGPS does not rely only on the current or past status of the scheduling process. By treating the possible solutions as points in a search space, the proposed HGPS through a genetically guided search visits and examines the possible solutions and estimates the impact of each these solution on overall performance of system in terms of fairness, throughput or QoS without actually performing a transmission. Subsequently, the solution that achieves the best estimated overall performance is chosen for the actual transmission. By means of computer simulation, performance of the HGPS algorithm is characterized in Rayleigh fading and shadowing radio channel conditions. The impact of imperfect reporting on the performance of HSDPA system is evaluated. We examine the joint impact of reporting latency, imperfect channel estimation and the corruption of reports in the feedback channel on the performance. It is shown that the proposed class of intelligent parallel random schedulers is highly robust against the imperfect reports from UEs. Acknowledgment The authors would like to acknowledge the valuable assistance provided by Mr Pierre Coulon of Fujitsu Laboratories of Europe Ltd.This work was presented in part at IEEE WPMC’2002, and will be presented in part at IEEE IST’2003.