一种适用于宽带无线城域网实时业务的分组调度算法

对宽带无线城域网（WMAN）而言,分组调度算法是保证用户服务质量（QoS）、平衡用户间公平性的关键。在研究比例公平调度算法（PF）算法与修正的最大加权时延优先算法（M-LWDF）的基础上,一种新的适用于宽带无线城域网实时业务的分组调度算法被提出,此算法引入了新的衡量服务队列负载的信息,能够实时地更新状态参数,提高了系统性能。仿真结果表明,此算法在保证系统吞吐量的同时,比M-LWDF算法具有更好的时延特性和公平性。     

MUMF-支持单多播公平服务的调度策略

基于联合输入交叉点排队(CICQ,combined input and cross-point queuing)交换结构探讨了单多播混合调度的公平性问题,提出了能够为单多播业务提供混合公平性的CICQ理想调度模型。基于理想调度模型,提出了逼近理想调度模型的MUMF(mixed uni-and multicast fair)调度算法,MUMF调度算法采用了分级和层次化的公平调度机制,通过输入调度和交叉点调度确保单多播业务混合调度的公平性。MUMF交换机制的每个输入、输出端口可独立地进行分组交换,具有良好可扩展特性。最后,基于SPES(switching performance evaluation system)的性能仿真结果表明MUMF调度算法具有良好的时延、公平性和吞吐量性能。     

基于模糊流感知的动态优先公平调度算法

为适应网络的动态性,提高调度公平性和资源效率,流感知优先公平调度机制需要动态的多业务区分转发。与链路负载状态相关的模糊流感知能够实现路径上的一致性业务区分,而基于模糊流感知的动态优先公平调度算法通过调整优先队列负载门限在流式流和弹性流之间实现转发优先权的动态交替,在链路轻载时实现不同流间的相对公平调度,在链路重载时则强调实时业务的绝对优先权以保证其时延要求。算法公平性分析和仿真计算显示提出算法的动态区分转发通过适度增加优先业务队长能够大幅度提高弹性流的接纳率,具有较高的链路平均吞吐量和资源效率。     

基于EPON的公平带宽分享算法及其应用

考虑光学开放接入网（optical open access network）中的公平性,将最大最小公平算法用到双向服务等级协议（D-SLA）中,提出了一种基于以太无源光学网络（EPON）的易于实现的双向服务等级协议公平带宽分配算法。算法使用了两轮分配,通过分级管理确定首要SLA和次要SLA,对业务提供商和用户进行分级区...     

LHFS-支持公平服务的CICQ混合调度策略

 针对现有联合输入交叉点排队交换结构(CICQ,Combined Input and Cross-point Queuing)调度策略无法提供基于"流"的服务质量保障,探讨了在CICQ交换结构实施基于流调度的可能性,提出一种能够为到达流提供公平服务的分层混合公平服务调度策略—LHFS(Layered and Hybrid Fair Scheduling).LHFS对每个输入、输出端口可独立地进行变长分组交换,其算法复杂度为O(1),具有良好可扩展特性.理论分析结果表明,LHFS能够为业务流提供时延上限和公平性保障.最后,基于SPES(Switching Performance Evaluation System)仿真系统对LHFS的性能进行了评估.     

3GPP LTE系统中无线视频传输调度算法研究

摘要：针对3GPP LTE系统,本文提出了适用于下行链路视频业务的一种新的分组调度算法,即时延优先比例公平调度（Delay First-Proportional Fair Scheduling,DF-PFS）。当需要做出调度决策时,该算法利用每个用户的数据包时延信息和瞬时下行信道条件,在满足用户QoS前提下最大限度地提高系统吞吐量。同时,当用户选择资源块（RB）进行传输后,即从用户集合中将该用户删除,避免接近eNodeB的用户一直占用无线资源,确保了资源分配的公平性。实验仿真结果表明,该算法在丢包率和PSNR性能上优于最大权重时延优先（M-LWDF）算法,在保证用户间公平性前提下,满足了视频业务的QoS要求。     

一种公平输入排队调度算法

输入排队交换结构以其良好的可扩展性被越来越多的高速交换机和路由器所采用。当前的调度算法大都以牺牲公平性来换取最大的吞吐量。但随着对QoS支持的要求增强,适用于输入排队交换结构的高效、公平的调度算法成为迫切需要解决的问题。该文提出了一种具有公平性保证的基于虚服务量的公平调度算法。理论分析和计算机仿真都表明算法在信元时延和公平性方面都能提供较好的保证。算法还具有与iSLIP相同的较低通信开销,以及和iLQF相同的算法复杂度。因此,算法具有较好的实用性。     

高效公平的EPON TCP性能调节机制

 提出了一个基于效用的EPON公平性指标算法.通过建立一个基于ACK特征包的ACK压缩和解压缩机制,消除了上游ONU的ACK对下游ONU下行数据流的影响,在保证ONU之间的公平性的同时,提高了带宽的使用效率.通过建立一个效用分类器,在维护了优先级机制扩展性的前提下,提高了并发的同业务类业务流之间的公平性.通过建立一个时延公平调度机制,在保证带宽的使用率前提下,保证了ONU的业务类之间的时延公平性.仿真结果很好验证了本机制的优点.     

分组公平调度算法的性能研究

本文针对不同的分组公平类调度算法(PFQ,Packet Fair Queuing),对它们在端到端的时延、时延抖动、公平性等服务质量(QoS)方面作了比较,并给出两种可以减少时标比较次数的方法,以简化它们在硬件上实现的复杂度.     

基于时延和速率效用函数的LTE无线资源调度算法研究

为了提高LTE实时业务调度的公平性,在M-LWDF资源调度算法的优先级判断机制中引入了平均传输速率和保证比特速率,将经济学中的效用思想和效用函数引入M-LWDF调度算法,提出了一种基于时延效用函数和速率效用函数的M-LWDF改进算法,更好地体现了调度算法的时延特性和速率特性。仿真结果表明基于时延和速率效用函数的M-LWDF调度算法具有更高的公平性,能够更好地满足对实时业务的调度要求。     

Carry-over round robin: a simple cell scheduling mechanism for ATMnetworks

We propose a simple mechanism named carry-over round robin (CORR) for scheduling cells in asynchronous transfer mode networks. We quantify the operational complexity of CORR scheduling and show that it is comparable to that of a simple round-robin scheduler. We then show that, albeit its simplicity, CORR is very competitive with much more sophisticated and significantly more complex scheduling disciplines in terms of performance. We evaluate the performance of CORR using both analysis and simulation, We derive analytical bounds on the worst case end-to-end delay achieved by a CORR scheduler for different traffic arrival patterns. Using traffic traces from MPEG video streams, we compare the delay performance of CORR with that of packet-by-packet generalized processor sharing (PGPS) and stop-and-go (SG). Our results show that, in terms of delay performance, CORR compares favorably with both PGPS and SG. We also analyze the fairness properties of CORR and show that it achieves near perfect fairness     

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.     

Latency-rate servers: a general model for analysis of trafficscheduling algorithms

We develop a general model, called latency-rate servers (ℒℛ servers), for the analysis of traffic scheduling algorithms in broadband packet networks. The behavior of an ℒℛ server is determined by two parameters-the latency and the allocated rate. Several well-known scheduling algorithms, such as weighted fair queueing, virtualclock, self-clocked fair queueing, weighted round robin, and deficit round robin, belong to the class of ℒℛ servers. We derive tight upper bounds on the end-to-end delay, internal burstiness, and buffer requirements of individual sessions in an arbitrary network of ℒℛ servers in terms of the latencies of the individual schedulers in the network, when the session traffic is shaped by a token bucket. The theory of ℒℛ servers enables computation of tight upper bounds on end-to-end delay and buffer requirements in a heterogeneous network, where individual servers may support different scheduling architectures and under different traffic models     

Solving the trade-off between fairness and throughput: Token bucket and leaky bucket-based weighted fair queueing schedulers

In this article, we present two efficient weighted fair queueing (WFQ) scheduling algorithms leaned on the well-known token bucket and leaky bucket shaping/policing algorithms. The performance of the presented algorithms is compared to those of the state-of-the-art WFQ approximations such as weighted round robin (WRR) and the recently proposed bin sort fair queueing (BSFQ). Our simulation results show that the proposed algorithms provide a better fairness at a lower implementation complexity while simultaneously achieving a comparable network utilization.     

Designing a fair scheduling mechanism for IEEE 802.11 wireless LANs

A fair scheduling mechanism called distributed elastic round robin (DERR) is proposed in this letter for IEEE 802.11 wireless LANs operated in a distributed manner. To quantify the fairness, we not only derive its fairness bound, but also observe the fairness through ratios of throughput and weight using a simulation approach. By numerical comparisons among DERR, distributed deficit round robin (DDRR), and IEEE 802.11e, we demonstrate that DERR outperforms the other two mechanisms in performance and fairness.     

Scheduling schemes for multimedia service in wireless OFDM systems

Scheduling schemes play a key role in the system performance of broadband wireless systems such as WLANs/WMANs. Maximal SNR and round robin are two conventional scheduling strategies that emphasize efficiency and fairness, respectively. The proportional fair scheme provides a trade-off between efficiency and fairness, and has been well studied in TDMA and CDMA systems. In this article we extended the PF scheduling scheme to OFDM-based BWSs (OPF). In addition, we propose three variations: adaptive OPF (AOPF), multimedia AOPF (MAOPF), and normalized MAOPF (NMAOPF) in order to meet the QoS requirements for multirate services in multimedia systems. The adaptive modulation and coding schemes in time varying and frequency selective fading are considered. The system performances of the algorithms are compared in terms of efficiency (throughput and mean packet delay) and fairness (user satisfaction rate and average user rate). Joint physical and media access control layer simulation results show that AOPF and MAOPF can improve throughput at the cost of fairness, and NMAOPF can provide the highest throughput without losing fairness.     

Fair round robin binary countdown to achieve QoS guarantee and fairness in WLANs

How to guarantee both quality of service (QoS) and fairness in wireless local area networks (WLANs) is a challenging issue. To touch this issue, a fair medium access control (MAC) scheme called fair round robin binary countdown (FRRBC) adopting the eminent concepts of allowance and binary countdown is proposed in this paper. FRRBC can guarantee QoS for both audio and video with the aid of adaptive adjustment on system parameters and some extra rules designed according to delay bounds. Using multiple mapping functions from allowances to fixed-bit binary numbers to indicate different priorities, FRRBC not only provides guaranteed system performance but also achieves good fairness. Finally, we demonstrate that FRRBC can significantly outperform the enhanced distributed channel access (EDCA) (IEEE 802.11 WG in IEEE Standard for Information technology—Telecommunications and information exchange between systems—Local and metropolitan area networks—Specific requirements—Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications. Amendment 8: Medium Access Control (MAC) Quality of Service Enhancements, 2005) and the synchronized medium access control (SYN-MAC) (Wu HY et al. in Mobile Netw Appl 11:627–637, 2005) because of its superiority to offer guaranteed QoS for both audio and video, low delay jitter, low blocking ratio, and good fairness. Of course, FRRBC can be illustrated to be a better choice than the enhanced distributed elastic round robin (EDERR) (Ferng HW, Liau HY in IEEE Trans Mobile Comput 8(7):880–894, 2009).     

An Improved Round Robin Packet Scheduler for Wireless Networks

Scheduling algorithms are important components for providing quality-of-service (QoS) guarantees in wireless networks. The design of such algorithms need to take into account bursty errors and location-dependent channel capacity that are characteristics of wireless networks. In this paper, a new scheduling algorithm for packet cellular networks, wireless deficit round robin (WDRR), is proposed. WDRR is a round robin scheduler that has low implementation complexity and offers a low delay bound, tight fairness index, and good isolation property. In error-prone channels, the algorithm provides short-term fairness among sessions that perceive a clean channel, long-term fairness among all sessions, ability to meet specified throughput objectives for all sessions, and graceful service degradation among sessions that received excess service. Both analysis and simulation are used to verify the WDRR properties.     

Delay Sensitive Smoothed Round Robin (DS2R2) Scheduler for High-Speed Optical Networks

Smoothed round robin (SRR) is an 0(1) scheduler that efficiently schedules flows based on flow granularity leading to short-term fairness. We propose DS2R2 - delay sensitive smoothed round robin scheduler that enhances SRR by adhering to delay constraints of flows. Scalability and performance issues of DS2R2 for high-speed optical networks are considered.     

Comments on “Carry-over round robin: a simple cell schedulingmechanism for ATM networks

Saha, Mukherjee, and Tripathi (see ibid., vol.6, no.6, p.779-796, 1998) present and analyze an ATM cell scheduling algorithm called carry-over round robin. Unfortunately, one of the basic lemmas in their paper, related to the performance of this algorithm, does not hold. This adversely affects the delay and fairness properties that they subsequently derive. To substantiate this, we describe carry-over round robin and present a counterexample to the lemma. We end with some concluding remarks