在CICQ交换结构下实现分布式的WFQ类加权公平调度算法

传统的基于crossbar的输入排队交换结构在提供良好的QoS方面存在很大的不足,而CICQ(Combined Input and Crosspoint buffered Queuing)交换结构与传统的交换结构相比,不但能在各种输入流下提供接近输出排队的吞吐率,而且能提供良好的QoS支持。该文基于CICQ结构,提出了在输入排队条件下实现基于流的分布式WFQ类分组公平调度算法的方案,并通过仿真验证了这一方案的有效性。     

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

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

CICQ交换结构中共享缓存的研究与应用

针对带缓存的的交叉开关(Combined Input and Crosspoint Buffered Queuing,CICQ)交换结构在多端口多优先级而引起的存储规模和面积开销增大的问题,提出了一种基于共享缓存思想的CICQ交换结构。它使用虚拟输入排队(VOQ)的方式,支持多优先级流控,并通过动态分配虚拟输出队列的方式设计队列管理结构,从而降低复杂度,减少对缓存区容量的需求。通过对各模块进行VHDL代码设计和使用Modelsim进行仿真,结果表明该结构能够实现交换结构数据的缓存。     

基于CICQ的新型并行交换结构研究

提出一种基于CICQ的支持区分服务的分布式并行分组交换结构(CDPPS, distributed CICQ based diffServ supporting parallel packet switch).通过使用多个低速交换设备来构建支持区分服务的并行分组交换,CDPPS解决了在高速环境下构建可行的区分服务调度问题.由于可以在不做任何改动的情况下将CICQ结构作为中间层平面,提高了现有资源的利用率.采用全分布式的调度算法,CDPPS避免了系统的通信开销,降低了硬件实现复杂度.理论分析和实验仿真表明,CDPPS能为各类业务提供满意的服务质量.     

一种基于缓存状态的CICQ交换机

CICQ (Combined Input and Cross-point-Queued switch)交换机是一种在交叉点缓存加入少量缓存的交换结构,是当前研究的一个热点。该文研究了基于交叉点缓存的各种调度算法和基于CICQ的交换结构,提出了LFF-LBF算法,运用通畅度和拥塞度两个概念,保证了最急迫的信元被最先服务。仿真分析表明该算法在均匀分布和突发业务源的情况下具有良好的时延性能和稳定性能。     

一种新型的负载均衡-交叉点缓冲交换结构

针对混合输入-交叉点队列(CICQ)交换结构受限于"流控通信延时"、"需要2倍内部加速仿真输出队列(OQ)交换"以及单纯交叉点缓冲(CQ)存在"非均衡流量模式下吞吐量性能不足"等问题,本文提出一种新型的"负载均衡交叉点缓冲交换结构".采用固定模式时隙轮转匹配进行负载均衡处理,将到达输入端口的非均衡流量转化为近似均衡流量并且平均分配到同一输出端口对应的交叉缓冲中,从而可以利用较小的交叉点缓冲来模拟输出队列调度,简化调度过程并且提高吞吐量.理论分析证明了这种新结构的稳定性以及模拟输出队列交换的能力.同时仿真表明,采用该交换结构可以在不需要内部加速的条件下获得相当于输出队列交换的性能,并且有效地解决了交叉点缓冲队列非均衡流量性能不足的问题.     

一种基于最长队列预测的CICQ交换结构调度算法

CICQ(Combined Input Crosspoint Queued)是一种在crossbar交叉点加入少量缓存的交换结构,具有无需内部加速比及分布并行调度的特性。为了自适应网络环境中各种业务流量,提高在非均匀流量下的性能,该文提出了一种基于最长队列预测的高效CICQ交换结构调度算法RR-LQD (Round Robin with Longest Queue Detecting)。RR-LQD算法复杂度为O(1),具有良好的可扩展性;通过预测局部最长队列并尽力为其服务,保持调度中队列长度的均衡,能够适应各种非均匀流量的网络环境。仿真结果表明:在各种均匀和非均匀流量下,RR-LQD算法均能达到100%的吞吐量,并且具有优良的时延性能。该文使用FPGA芯片实现了RR-LQD算法仲裁器,能够满足高速、大容量交换结构的设计需要。     

一种可提供QoS保障的新型交换结构

本文采用带缓存交叉开关作为核心交换单元,构建了一种空分复用扩展的联合输入/交叉节点/输出排队(SDM-CICOQ)交换结构,从理论上证明了当扩展因子为2时,SDM-CICOQ交换结构可以获得100%的吞吐量,并且能够完全模拟输出排队(OQ)交换结构,从而能够提供服务质量(QoS)保障.本文还给出了一种层次化优先级调度(HPS)方案作为SDM-CICOQ交换结构调度机制的工程设计参考,仿真结果表明采用HPS调度方案SDM-CICOQ交换结构可获得良好的性能.     

带VOQ的输入队列交换网络中的分组调度算法研究

交换技术已经成为高速路由器的核心技术。本文基于目前高速交换技术所采用的主要体系结构,带有虚拟输出缓冲队列(VOQ)的输入队列交换结构,分析已经存在的各种调度算法的性能,并设计基于遗传算法的调度策略,提供IP数据网络的QoS对吞吐量和抖动的保障。     

输入排队结构交换机分组调度研究

以决定分组调度算法的交换结构为基础,从协调,减少和隔离输入排队交换结构中输入输出竞争裁决冲突的角度,分别讨论了VOQ,CIOQ,CICQ结构中的分组调度问题,并以当前最新的调度算法为例加以说明,进行了定性分析和定量对比,指出了具体有待研究的问题。随后讨论了最近才开始研究的光电混合结构中的分组调度问题。最后从交换结构和算法两个方面探讨了今后的研究方向和发展趋势。     

一种用于IEEE 802.16无线城域网TDD模式中的带宽调度方案

该文提出了一种用于IEEE 802.16宽带无线接入系统TDD模式下的公平而有效的带宽分配调度体系。与该领域中传统的固定带宽分配方式相比,该文提出的调度体系结构综合考虑了上下行链路不同业务带宽需求并进行动态带宽分配。该文提出一种新的亏空公平优先级队列(DFPQ)算法来调度不同优先级的业务流,可以为系统提供更好的公平性。仿真结果显示该文提出的调度体系结构能够很好地满足所有类型业务的服务质量(QoS)需求,并提供较好的公平性。     

Traffic and Interference Adaptive Scheduling for Internet Traffic in UMTS

In this paper we propose a scheduling strategy for the radio resources management when transmitting Internet traffic over third-generation systems. More precisely, we consider the UMTS Terrestrial Radio Access Network (UTRAN) Time Division Duplex (TDD) mode standardized by ETSI. UTRAN TDD uses a hybrid solution of code and time division multiple access, called TD-CDMA. In UMTS systems a key issue in developing access methodologies for the available spectrum is an optimal management of the rare radio resources. In this paper we present a fair and efficient scheduling algorithm that adapts its behavior to traffic and interference conditions. Specifically, our scheduling algorithm is able to manage the radio resources taking into account both the traffic fluctuations in the uplink and downlink direction and the variations of the system interference. The goal of our scheduler is the data-throughput maximization for an efficient utilization of available radio resources. The effectiveness of our scheduling algorithm is shown by exploiting analytical tools.     

A unified framework for opportunistic fair scheduling in wireless networks: a dual approach

In this paper, we propose a unified framework for opportunistic fair scheduling in wireless systems. We consider a TDMA type of multiple access scheme, in which only one user can be scheduled in each time-slot. For opportunistic fair scheduling in such a system, some nice frameworks have been developed in the previous works, such as Agrawal and Subramanian (Allerton conference on communication, control and computing, 2002), Liu et al. (IEEE Journal of Selected Areas in Communications 19(10): 2053–2065, 2001) and Liu et al. (Computer Networks 41(4): 451–474, 2003). However, in this paper, we consider a more general problem that can accommodate more general types of fairness, and more general types of utility functions than those in the previous works. In addition to those generalizations, we develop a new framework for opportunistic fair scheduling based on the duality theory, which is different from those in the previous works. The duality theory is a well-defined theory in the mathematical optimization area. Hence, it can provide a unified framework for many different types of problems. In fact, we show that two different frameworks in Agrawal and Subramanian (Allerton conference on communication, control and computing, 2002), Liu et al. (IEEE Journal of Selected Areas in Communications 19(10): 2053–2065, 2001) and Liu et al. (Computer Networks 41(4): 451–474, 2003) are special cases of ours. In addition, by using the unified framework developed in this paper, we can not only develop various opportunistic fair scheduling schemes but also analyze the developed algorithm more rigorously and systematically.     

Distributed Proportional Fair Scheduling for IEEE802.11 Wireless LANs

In the time varying wireless channel, opportunistic scheduling is one of the important techniques to achieving the rich diversities inherent in wireless communications. However, most existing scheduling schemes require centralized scheduling and little work has been done on developing distributed algorithms The proportional fair scheduling is one of the representative opportunistic scheduling for centralized networks. In this paper, we propose distributed proportional fair scheduling (DPFS) scheme for wireless LAN network. In the proposed DPFS scheme, each receiver estimates channel condition and calculates independently its own priority with probabilistic manner, which can reduce excessive probing overhead required to gather the channel conditions of all receivers. We evaluate the proposed DPFS using extensive simulation and simulation results show that DPFS obtains higher network throughput than conventional scheduling schemes while maintaining fairness among users.     

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.     

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 a fair scheduler exploiting multiuser diversity with feedback information reduction

In this letter, we propose a new downlink fair scheduling scheme exploiting the multiuser diversity to enhance the transmission capacity. In the proposed scheme, only the MSs (mobile stations) whose normalized SNR (signal-to-noise ratio) values are larger than a given threshold feedback one-bit information to the BS (base station). As a result, while achieving the strict fairness, the proposed scheme can efficiently utilize the spectrum by reducing the considerable amount of the feedback information, compared to the proportional fair scheduling scheme where all the MSs feed back the normalized SNR values to the BS. Numerical studies show that the transmission capacity in the proposed scheme with a suitable value of the threshold is very close to that in the proportional fair scheduling scheme.     

输入队列交换的公平可扩展调度系统

提出了一种基于输入队列交换的公平可扩展网络调度系统FSSA.通过将若干个容量较小的调度器合理连接并使其协同工作,构成多端口大容量网络交换调度系统,解决了单个调度器容量和端口数受集成电路工艺限制的问题.FSSA不仅速度高、规模可扩展而且易于硬件实现.环型连接、管线工作及公平调度技术的采用使FSSA在性能方面得到了进一步优化.仿真结果显示,FSSA的性能可与基于iSLIP、DSRR等算法的单片调度器相比拟,尤其在流量较大时,FSSA的性能明显优于单调度器性能.     

Frame‐based adaptive uplink scheduling algorithm in orthogonal frequency division multiple access‐based Worldwide Interoperability for Microwave Access networks

Because the orthogonal frequency division multiple access physical resource available for scheduling in Worldwide Interoperability for Microwave Access networks is frame by frame, an uplink scheduler located at the base station must efficiently allocate available resources to the subscriber stations in response to constant or bursty data traffic on a per‐frame basis. Available resources for real‐time and nonreal‐time traffics, called frame‐based adaptive bandwidth allocation and minimum guarantee and weight‐based bandwidth allocation, respectively, are proposed in this paper. Moreover, both short‐term and long‐term bandwidth predictions for traffic are incorporated so that the long‐term bandwidth prediction can have sustainable throughput requirement, and the short‐term bandwidth prediction can meet the objectives of low delay and jitter. For the scenarios studied, it shows that system performance of the proposed algorithm is better than the hybrid (earliest deadline first + weighted fair queuing + FIFO) algorithm in terms of packet delay, jitter, throughput, and fairness. Copyright © 2011 John Wiley & Sons, Ltd.     

On the optimality of multiantenna broadcast scheduling using zero-forcing beamforming

Although the capacity of multiple-input/multiple-output (MIMO) broadcast channels (BCs) can be achieved by dirty paper coding (DPC), it is difficult to implement in practical systems. This paper investigates if, for a large number of users, simpler schemes can achieve the same performance. Specifically, we show that a zero-forcing beamforming (ZFBF) strategy, while generally suboptimal, can achieve the same asymptotic sum capacity as that of DPC, as the number of users goes to infinity. In proving this asymptotic result, we provide an algorithm for determining which users should be active under ZFBF. These users are semiorthogonal to one another and can be grouped for simultaneous transmission to enhance the throughput of scheduling algorithms. Based on the user grouping, we propose and compare two fair scheduling schemes in round-robin ZFBF and proportional-fair ZFBF. We provide numerical results to confirm the optimality of ZFBF and to compare the performance of ZFBF and proposed fair scheduling schemes with that of various MIMO BC strategies.