基于SP调度策略的簇树型无线传感网络QoS上界研究

为了改善无线传感网络在最坏条件下的网络服务质量（Quality of Service, QoS）,本文将严格优先级（Strict Priority, SP）队列调度引入簇树型无线传感网络中,分析SP队列调度对网络中数据流获得的保证服务的影响,并利用网络演算推导簇树网络中各深度路由节点的时延上界、缓存上界及网络的端到端时延上界。通过实例分析,表明SP队列调度能够有效减小网络的最大端到端时延。     

I/O issues in a multimedia system

In future computer system design, I/O systems will have to support continuous media such as video and audio, whose system demands are different from those of data such as text. Multimedia computing requires us to focus on designing I/O systems that can handle real-time demands. Video- and audio-stream playback and teleconferencing are real-time applications with different I/O demands. We primarily consider playback applications which require guaranteed real-time I/O throughput. In a multimedia server, different service phases of a real-time request are disk, small computer systems interface (SCSI) bus, and processor scheduling. Additional service might be needed if the request must be satisfied across a local area network. We restrict ourselves to the support provided at the server, with special emphasis on two service phases: disk scheduling and SCSI bus contention. When requests have to be satisfied within deadlines, traditional real-time systems use scheduling algorithms such as earliest deadline first (EDF) and least slack time first. However, EDF makes the assumption that disks are preemptable, and the seek-time overheads of its strict real-time scheduling result in poor disk utilization. We can provide the constant data rate necessary for real-time requests in various ways that require trade-offs. We analyze how trade-offs that involve buffer space affect the performance of scheduling policies. We also show that deferred deadlines, which increase buffer requirements, improve system performance significantly     

Allocating fixed-priority periodic tasks on multiprocessor systems

In this paper, we study the problem of allocating a set of periodic tasks on a multiprocessor system such that tasks are scheduled to meet their deadlines on individual processors by the Rate-Monotonic scheduling algorithm. A new schedulability condition is developed for the Rate-Monotonic scheduling that allows us to develop more efficient on-line allocation algorithms. Two on-line allocation algorithms—RM-FF and RM-BF are presented, and shown that their worst-case performance, over the optimal allocation, is upper bounded by 2.33 and lower bounded by 2.28. Then RM-FF and RM-BF are further improved to form two new algorithms: Refined-RM-FF (RRM-FF) and Refined-RM-BF (RRM-BF), both of which have a worst-case performance bound of 2. We also show that when the maximum allowable utilization of a task is small, the worst-case performance of all the new algorithms can be significantly improved. The worst-case performance bounds of RRM-FF and RRM-BF are currently the best bounds in the class of on-line scheduling algorithms proposed to solve the same scheduling problem. Simulation studies show that the average-case performance of the newly proposed algorithms is significantly superior to those in the existing literature.     

Maximum allowable delay bounds of networked control systems

This paper proposes a new method to obtain a maximum allowable delay bound for a scheduling of networked control systems. The proposed method is formulated in terms of linear matrix inequalities and can give a much less conservative delay bound than the existing methods. A network scheduling method is presented based on the delay obtained through the proposed method, the bandwidth of a network is allocated to each node and the sampling period of each sensor and controller is determined. The presented method can handle three types of data (periodic data, sporadic data, and message) and guarantees real-time transmission of periodic and sporadic data, and minimum network utilization for non-real time message.     

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.     

Real-time scheduling method for networked discrete control systems

This paper proposes a new scheduling method to obtain a maximum allowable delay bound for a scheduling of networked discrete control systems. The proposed method is formulated in terms of linear matrix inequalities (LMI) and can give a much less conservative delay bound than the existing methods. An event based network scheduling method is presented based on the delay bound obtained through the proposed method, and it can adjust the sampling period to allocate identical utilization to each control loop. The presented method can handle sporadic emergency data, periodic data, and non-real-time data.     

AHPS:公平的混合包调度策略

在综合服务模型中非实时通信虽然不要求严格的服务质量保证,但是它承担着绝大多数网络应用,因而传输性能的影响更广泛。目前用于保证实时连接的服务质量的速率比例包调度算法不能公平地处理非实时通信和实时连接,允许实时连接的通信量任意地抢占未预约带宽,使得非实时通信的传输性能恶化。自适应混合包调度算法不仅保证实时连接的服务质量,而且通过限制实时连接的非协议通信量对网络资源的占用,优化了非实时通信的传输性能,提高了带宽资源的效率。     

Rate control of multi class priority flows with end-to-end delay and rate constraints for QoS networks

To address end-to-end quality of service (QoS) requirements, we derive a novel distributed combined rate and end-to-end delay control in a network serving multi-class flows with priority packet scheduling. We show that the control is globally asymptotically stable without information time lags. The stable flows attain the end-to-end delay requirements and have no packet loss. We also show that by enhancing the network with bandwidth reservation and admission control, minimum rate is also guaranteed. The stability with very long time lags of a discrete time version control with non-greedy flows and random packet arrivals is studied numerically by an NS2 packet-based simulation of the Australian Academic and Research Network.     

A robust packet scheduling algorithm for proportional delay differentiation services

Proportional delay differentiation (PDD) model is an important approach to relative differentiated services provisioning on the Internet. It aims to maintain pre-specified packet queueing-delay ratios between different classes of traffic at each hop. Existing PDD packet scheduling algorithms are able to achieve the goal in long time-scales when the system is highly utilized. This paper presents a new PDD scheduling algorithm, called Little’s average delay (LAD), based on a proof of Little’s Law. It monitors the arrival rate of the packets in each traffic class and the cumulative delays of the packets and schedules the packet according to their transient queueing properties in order to achieve the desired class delay ratios in both short and long time-scales. Simulation results show that LAD is able to provide predictable and controllable services in various system conditions and that such services, whenever feasible, can be guaranteed, independent of the distributions of packet arrivals and sizes. In comparison with other PDD scheduling algorithms, LAD can provide the same level of service quality in long time-scales and more accurate and robust control over the delay ratio in short time-scales. In particular, LAD outperforms its main competitors significantly when the desired delay ratio is large.     

The service curve service discipline for the rate-controlled EDF service discipline in variable-sized packet networks

Guaranteed service will provide high quality services to real-time applications, e.g., audio or video, over packet networks such as the Internet. To support guaranteed service, a service discipline must guarantee a delay bound to each session. In addition, a preferred service discipline should achieve high network utilization and good scalability. The service disciplines studied so far have problems in achieving these two objectives at the same time. Generalized processor sharing (GPS) service disciplines can have low network utilization. Rate-controlled (RC) service disciplines have difficulty in scalability because of regulators. For service curve (SC) service disciplines, both the network utilization and the scalability depend on the adopted SC. To date, there have been no studies on an SC which can make an SC discipline achieve these two objectives. We propose a new service discipline based on SC service disciplines. The proposed discipline achieves these two goals in a variable-sized packet environment. We show that the discipline can achieve the network utilization achievable by the RC service disciplines. We further show that our SC requires O(1) complexity for deadline calculation. Different from the RC service disciplines, the SC service discipline with our SC does not need regulators at all. Thus, it has better scalability than the RC service disciplines and is work-conserving. We also show that the proposed SC makes SC service disciplines have strictly higher network utilization than the GPS service disciplines including the multi-rate service discipline.     

Switch cost and packet delay tradeoff in data center networks with switch reconfiguration overhead

Cost minimization is a major concern in data center networks (DCNs). Existing DCNs generally adopt Clos network with crossbar middle switches to achieve non-blocking data switching among the servers, and the number of middle switches is proportional to the number of ports of the aggregation switches in a fixed manner. Besides, reconfiguration overhead of the switches is generally ignored, which may contradict the engineering practice. In this paper, we consider batch scheduling based packet switching in DCNs with reconfiguration overhead at each middle switch, which inevitably leads to packet delay. With existing state-of-the-art traffic matrix decomposition algorithms, we can generate a set of permutations, each of which stands for the configuration of a middle switch. By reconfiguring each middle switch to fulfill multiple configurations in parallel with others, we reveal that a tradeoff exists between packet delay and switch cost (denoted by the number of middle switches), while performance guaranteed switching with bounded packet delay can be achieved without any packet loss. Based on the tradeoff, we can minimize the number of middle switches (under a given packet delay bound) and an overall cost metric (by translating delay into a comparable cost factor), as well as formulating criteria for choosing a proper matrix decomposition algorithm. This provides a flexible way to reduce the number of middle switches by slightly enlarging the packet delay bound.     

一种提供延迟保证的多级FIFS队列包调度算法

包调度算法是提供服务质量保证的一个重要部分.传统的每流区分的包调度方法通常不能支持较好的扩展性,不适应当前网络带宽的迅速增长.而非每流区分的方法又不能提供每流的服务保证.动态包状态(dynamic packet state,简称DPS)方法提供了一种在无须维护每流状态下提供保证服务的方法,该方法在保证服务质量的同时大大提高了扩展性.但是它仍然需要每包的调度,其复杂度和包的数量有关.在DPS的基础上提出了一种用多级FIFS队列提供延迟保证的包调度算法,并给出了该算法实现服务保证的约束条件.理论分析和仿真实验结果都表明:该算法可以实现常数时间的包调度复杂性,同时具有和DPS同样的延迟性能.     

基于网络演算计算保证服务端到端延迟上界

归纳总结了网络演算,阐明了网络演算的两个基本工具——进入曲线和服务曲线,得出了服务曲线存在瓶颈效应、端到端延迟的理想与近似确定性上界、提供保证服务网络节点的服务曲线需求等结论,计算了服务曲线以速率等待时间及PGPS(packetizedgeneralizedprocessorsharing)形式表示的保证服务端到端延迟确定性上界.     

A performance study of uplink scheduling algorithms in point-to-multipoint WiMAX networks

The IEEE 802.16 standard defines the specifications for medium access control (MAC) and physical (PHY) layers of WiMAX networks. A critical part of the MAC layer specification is packet scheduling, which resolves contention for bandwidth and determines the transmission order of users. Evaluating the performance packet scheduling algorithms is of utmost importance towards realizing large-scale WiMAX deployment. In this paper, we conduct a comprehensive performance study of scheduling algorithms in point-to-multipoint mode of OFDM-based WiMAX networks. We first make a classification of WiMAX scheduling algorithms, then simulate a representative number of algorithms in each class taking into account that vital characteristics of the IEEE 802.16 MAC layer and OFDM physical layer. We evaluate the algorithms with respect to their abilities to support multiple classes of service, providing quality of service (QoS) guarantees, fairness amongst service classes and bandwidth utilization. To the best of our knowledge, no such comprehensive performance study has been reported in the literature. Simulation results indicate that none of the current algorithms is capable of effectively supporting all WiMAX classes of service. We demonstrate that an efficient, fair and robust scheduler for WiMAX is still an open research area. We conclude our study by making recommendations that can be used by WiMax protocol designers.     

WiMAX Mesh网络中一种分布式时隙分配算法

提出了一种基于资源预留的WiMAX Mesh网络支持QoS的微时隙动态分配算法。通过区分数据流优先级的方式将业务分为高优先级业务和低优先级业务两类,对高优先级的业务在每帧中预留一定的微时隙作为分配高优先级业务的时隙,预留时隙大小可以根据网络时隙使用状态动态地进行调整。仿真表明该算法在满足高优先级业务QoS的同时兼顾业务的请求失败率与时隙的利用率,降低了分组的平均时延。     

Measurement-based characterization and classification of QoS-enhanced systems

Quality-of-service mechanisms and differentiated service classes are increasingly available in networks and Web servers. While network and Web server clients can assess their service by measuring basic performance parameters such as packet loss and delay, such measurements do not expose the system's core QoS functionality such as multiclass service discipline. In this paper, we develop a framework and methodology for enabling network and Web server clients to assess system's multiclass mechanisms and parameters. Using hypothesis testing, maximum likelihood estimation, and empirical arrival and service rates measured across multiple time scales, we devise techniques for clients to: 1) determine the most likely service discipline among earliest deadline first, class-based weighted fair queuing, and strict priority; 2) estimate the system's parameters with high confidence; and (3) detect and parameterize non work-conserving elements such as rate limiters. We describe the important role of time scales in such a framework and identify the conditions necessary for obtaining accurate and high confidence inferences.     

基于统计移位排序结构的高速路由器公平队列调度算法实现

高速化和多媒体化是未来网络的主要发展方向,为了给用户提供可靠的端到端服务质量保证,通常需要在网络的中继节点上引入基于流的队列调度机制。WF^2Q＋队列调度算法即是一种性能优异同时又易于实现的公平队列调度算法。文中提出了一种基于统计移位排序结构的WF^2Q＋算法高速硬件实现方法,该方法充分利用队列的统计信息,以相对较少的硬件资源实现了统计意义上的快速完全排序。FPGA实现的结果表明,该结构可以应用于端口速率为OC－48的高速IP路由器上。     

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     

Upper-level scheduling supporting multimedia traffic in cellular data networks

Wireless data networks such as cdma2000 1x EV-DO and UMTS HSDPA use downlink scheduling that exploits channel fading to increase the system throughput. As future wireless networks will eventually support multimedia and data traffic together, we need a proper criterion for scheduling that can count various service requirements such as delay and packet loss. Although some previous approaches proposed opportunistic schedulers at the lower layer, it has not been investigated well whether they are able to meet explicit QoS defined at the upper layer. Hence, in this paper, we develop a hierarchical scheduling model that considers QoS provisioning and the time-varying channel feature separately. We focus on the upper-level QoS scheduling that supports various traffic classes in a unified manner. Supposing that a user gets some satisfaction or utility when served, we introduce a novel concept of opportunity cost, which is defined as the maximum utility loss among users incurred by serving a particular user at the current turn. We obtain each user’s net profit by subtracting the opportunity cost from its expected utility, and then select a user with the maximum profit for service. Simulation results reveal that our scheme supports various QoS classes well that are represented by delay and packet loss under various traffic loadings.