一种维序的基于组合输入输出排队的并行交换结构

提出一种按序排队(in-order queuing,简称IOQ)PPS体系结构,通过在分流控制器引入固定尺寸的缓冲区,实现负载在每个交换平面的均匀分配;中间层组合输入输出排队(combined input-and-output queuing,简称CIOQ)交换平面受控于中央调度器,在每个时间槽(timeslot),中央调度器将同一种匹配实施到每一个交换平面,称之为同步调度策略.可以证明,在该体系结构下,轮询(round robin)分派算法配合同步调度策略可以保证同一条流的信元按序从交换平面读出.进一步提出了严格最长队列优先同步调度算法,极大地减少了中央调度器需要维护的状态信息和信元重定序开销.与目前主流的PPS设计相比,IOQPPS(in-order queuing parallel packet switch)实现机制简单,易于硬件实现.模拟结果表明,IOQPPS具有最优的延迟性能.     

一种快速的主动网络信包调度机制

针对主动网络执行主动代码,处理主动信包的特点,该文提出了一种多优先级最短信包优先调度机制。该机制的结构由包分类器、缓冲管理器、缓冲队列和队列调度器组成。包分类器根据预先约定的规则对接收到的信包进行分类;缓冲管理器按照优先级将信包分发到相应的队列,并根据该信包长度遵循从小到大的顺序插入到队列中相应的位置;缓冲队列缓冲存储信包;队列调度器在相对优先级和时延两个方面均进行控制。实验结果表明该调度机制符合主动网络的特点,能够对主动网络中的信包进行快速、有效地调度处理。     

Modeling and performance analysis for IPv6 traffic with multiple QoS classes

This paper focuses on the modeling and performance analysis for IPv6 traffic with multi-class QoS in virtual private networks (VPN). The multi-class QoS is implemented on differentiated service basis using priority scheme of 4 bits defined in the packet header of IPv6. A VPN-enabled IP router is modeled as a tandem queuing system in which each output link consists of two parallel priority output queues. The high-priority queue is used to carry the delay sensitive traffic while the low-priority queue is used to carry the delay insensitive traffic. On the other hand, multiple thresholds are implemented in each queue, respectively, for packet loss priority control. The performance analysis is done using fluid flow techniques. The numerical results obtained from the analysis show that the differentiated service based on the priority schemes defined in IPv6 is able to effectively satisfy the multi-class QoS requirement for supporting multimedia services in VPN. The performance trade-off between the delay sensitive traffic and delay insensitive traffic in terms of traffic throughput, packet loss probability and end-to-end delay in VPN networks is presented.     

一种排队延迟感知的LTE调度机制

长期演进(LTE)系统在分组交换域内承载语音业务,但对延迟和丢包敏感的语音业务服务质量较难得到保证。为此,提出一种排队延迟感知的语音分组调度机制,根据队列长度、信道条件、排队延迟以及业务最大允许延迟来确定用户调度优先级,从而实现用户资源的合理分配。理论分析和仿真结果表明,与VSM调度机制相比,该调度机制在确保时延和系统吞吐量满足要求的前提下,能有效地利用网络资源,降低丢包率,提高用户公平性。     

A Comparison of Mamdani and Sugeno Fuzzy Based Packet Scheduler for MANET with a Realistic Wireless Propagation Model

 The mobile nature of the nodes in a wireless mobile ad-hoc network (MANET) and the error prone link connectivity between nodes pose many challenges. These include frequent route changes, high packet loss, etc. Such problems increase the end-toend delay and decrease the throughput. This paper proposes two adaptive priority packet scheduling algorithms for MANET based on Mamdani and Sugeno fuzzy inference system. The fuzzy systems consist of three input variables: data rate, signal-to-noise ratio (SNR) and queue size. The fuzzy decision system has been optimised to improve its efficiency. Both fuzzy systems were verified using the Matlab fuzzy toolbox and the performance of both algorithms were evaluated using the riverbed modeler (formally known as OPNET modeler). The results were compared to an existing fuzzy scheduler under various network loads, for constant-bit-rate (CBR) and variable-bit-rate (VBR) traffic. The measuring metrics which form the basis for performance evaluation are end-to-end delay, throughput and packet delivery ratio. The proposed Mamdani and Sugeno scheduler perform better than the existing scheduler for CBR traffic. The end-to-end delay for Mamdani and Sugeno scheduler was reduced by an average of 52% and 54%, respectively. The performance of the throughput and packet delivery ratio for CBR traffic are very similar to the existing scheduler because of the characteristic of the traffic. The network was also at full capacity. The proposed schedulers also showed a better performance for VBR traffic. The end-to-end delay was reduced by an average of 38% and 52%, respectively. Both the throughput and packet delivery ratio (PDR) increased by an average of 53% and 47%, respectively. The Mamdani scheduler is more computationally complex than the Sugeno scheduler, even though they both showed similar network performance. Thus, the Sugeno scheduler is more suitable for real-time applications.     

Design and Analysis of a Multiscale Active Queue Management Scheme

Since Internet is dominated by TCP-based applications, active queue management （AQM） is considered as an effective way for congestion control. However, most AQM schemes suffer obvious performance degradation with dynamic traffic. Extensive measurements found that Internet traffic is extremely bursty and possibly self-similar. We propose in this paper a new AQM scheme called multiscale controller （MSC） based on the understanding of traffic burstiness in multiple time scale. Different from most of other AQM schemes, MSC combines rate-based and queue-based control in two time scales. While the rate-based dropping on burst level （large time scales） determines the packet drop aggressiveness and is responsible for low and stable queuing delay, good robustness and responsiveness, the queue-based modulation of the packet drop probability on packet level （small time scales） will bring low loss and high throughput. Stability analysis is performed based on a fluid-flow model of the TCP/MSC congestion control system and simulation results show that MSC outperforms many of the current AQM schemes.     

Embedded fuzzy expert system for Adaptive Weighted Fair Queueing

This paper introduces an embedded fuzzy expert system for Adaptive Weighted Fair Queueing (AWFQ) located in the network traffic router to update weights for output queues. WFQ algorithm allows differentiated service for traffic classes according to Quality of Service (QoS) requirements. Link sharing and packet scheduling methods are the most critical factors when guaranteeing QoS. There are many different scheduling mechanisms but adequate and adaptive QoS aware scheduling solutions are still in a phase of development due to the rapid growth of multimedia in the Internet. The proposed AWFQ model in this work simplifies the link sharing to two service classes: one for UDP and another for TCP. The implementation of the model is based on adaptive change of weight coefficients that determine the amount of allowed bandwidth for the service class. New weight coefficients are calculated periodically on routers according to developed embedded fuzzy expert system. It is shown through simulations that the AWFQ model is more stable and reacts faster to different traffic states than the traditional WFQ scheduler. The embedded expert system adjusts the weights of AWFQ with two parameters that are based on the share of the UDP and TCP input traffic data rate and the change of the share of the UDP and TCP input data rate.     

动态调整调度配额的TCSN调度算法*

针对列车控制与服务网（TCSN）的区分服务需求,进行了调度算法研究,提出了一种基于动态调整调度配额的算法DWDRR。该算法在原有的WDRR（加权差额轮询算法）算法基础上增加了调度配额的计算,并根据队列的数据流量到达率、时延优先级、丢包优先级和网络的当前状况综合地决定各个队列的调度配额,实现比例公平的调度。并通过仿真分析证明该调度算法可以根据各队列在不同网络状态下流量到达率、优先级动态地决定队列的调度配额,从而满足TCSN根据不同到达率、优先级进行区分服务的需求。     

Designing and implementing a fast crossbar scheduler

Crossbar switches frequently function as the internal switching fabric of high performance network switches and routers. However, for fairness and high utilization, a crossbar needs an intelligent, centralized scheduler. We describe the design and implementation of a scheduling algorithm for configuring crossbars in input queued switches that support virtual output queues and multiple priority levels of unicast and multicast traffic. We carried out this design for Stanford University's Tiny Tera prototype, a fast, label-swapping packet switch. Its scheduler, designed to configure a crossbar once every 51 ns, implements the ESLIP scheduling algorithm, which consists of multiple round-robin arbiters     

一种基于模糊神经网络的可靠流量控制模型

为控制P2P流量,本文从数据缓冲区使用的实时状态出发,提出了一种基于模糊神经网络的拥塞控制模型,该模型把缓冲区划分为两个队列分别存放P2P和非P2P的数据包,通过模糊神经网络预测评估缓冲区队列的拥塞状况,并建立一个评估函数对各队列的空间分配作出指导,使得能够控制各队列的拥塞状况,并动态的调整缓冲区队列的分配,在缓冲区溢出前主动丢包,避免缓冲区锁定。模拟实验的结果表明,该模型在保证网络资源分配的公平性方面取得了较好的效果,它降低了数据包排队延时和丢包率,提高了路由器处理网络拥塞的能力。     

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.     

The effect of queuing representations on modeling transit signal priority systems in mixed mode operation

This paper examines quantitatively the effect of modeling assumptions on transit signal priority (TSP) control in mixed mode operation. The primary sources of delays to buses at intersections are queues formed at intersections (queuing delay) and traffic signals (signal delay). We show that models based on point queues and models based on spatial queues would lead to different control strategies and yield different results for the benefit to buses in terms of delay reduction. Situations in which the spatial content of queues is crucial to modeling TSP systems are identified in the paper. We conclude that given that models with the spatial queue representation are more realistic in capturing the queuing dynamics at intersections they should be incorporated in the decision‐making process for initiating priority calls in a TSP system.     

模糊反馈控制实时调度算法

为了解决模糊不确定任务集在不可预测环境下的动态抢占调度问题,应用模糊规则和模糊调度理论,提出一个基于模糊反馈控制的调度算法,并建立相应的调度架构.该架构由基本调度器和模糊反馈控制两部分组成.用模糊调度算法作为基本调度器的调度算法,将任务集按不同优先级等级进行划分,优先级等级高的任务优先调度,从而使得更多的重要任务得到调度;模糊控制器与任务流调节策略一起构成模糊反馈控制部分.仿真结果表明,模糊反     

Controlling mean queuing delay under multi-class bursty and correlated traffic

This paper presents an adaptive queue management scheme to maintain queuing delay in a router at a required level based on a comprehensive analytical model under aggregated Internet traffic flows from various traffic classes. The proposed scheme uses a closed-loop feedback control mechanism to constrain the average queuing delay by regulating traffic arrival rate implicitly through a movable queuing threshold. A discrete-time queuing model is developed to derive the relationship between average queuing delays and queuing thresholds based on a traffic model that models aggregated Internet traffic through superposition of N MMBP-2 arrival processes. The queuing threshold is adjusted dynamically with reference to the relationship derived in the analytical model and also feedback of average queuing delay measurement. Packets are dropped dynamically with respect to the changes of queuing threshold and the packet loss events serve as implicit congestion indicators. Matlab is used to perform queuing analysis and simulation. Statistical evaluation is performed to show the efficiency and accuracy of the analytical and simulation results.     

Design and performance evaluation of a fuzzy based traffic conditioner for differentiated services

The current Internet can only provide the best-effort services. By growing the Internet and its applications, new services with different requirements are developed. The differentiated services (Diffserv) [S. Blake, M. Carlson, E. Davies, Z. Wang, W. Weiss, An Architecture for Differentiated Services, IETF RFC 2475, 1998; K. Nichols, V. Jacobson, L. Zhang, A Two-bit Differentiated Services Architecture for the Internet, IETF RFC 2638, July 1999; T. Li, Y. Rekhter, A Provider Architecture for Differentiated Services and Traffic Engineering (PASTE), IETF RFC 2430, October 1998] is a scalable model for providing end-to-end quality of services. A Diffserv router consists of different components including classifier, meter, marker, dropper, shaper and scheduler. In this paper, we use the benefits of the fuzzy logic controller to design a fuzzy based traffic conditioner for Internet differentiated services. Our proposed model consists of three major parts: a fuzzy meter/marker (FM), a fuzzy active queue management (FAQM) algorithm and a fuzzy scheduler (FS). The proposed FM used to measure and mark the input traffic is based on the single rate three colors meter (srTCM) mechanism [J. Heinane, et al., A Single Rate Three Color Marker, RFC 2697, September 1999]. The FM meters an IP packet stream and marks its packets GREEN, YELLOW, or RED. The proposed FAQM is a fuzzy implementation of the well-known BLUE active queue management (AQM) algorithm [W. Feng, D. Kandlur, D. Saha, K. Shin, BLUE: A New Class of Active Queue Management Algorithms U. Michigan CSE-TR-387-99, April 1999]. To achieve a good throughput and reasonable packet loss ratio, the proposed FAQM mechanism employs a fuzzy logic controller. The third part of the proposed fuzzy traffic conditioner is FS. It is based on the traditional weighted fair queue (WFQ) mechanism [A. Demers, S. Keshav, S. Shenker, Analysis and simulation of a fair queueing algorithm, in: SIGCOMM Symposium on Communications Architectures and Protocols, Austin, Texas, September 1989, pp. 1–12] that tunes the weight of each queue by a fuzzy logic controller. To evaluate the performance of the proposed model, we developed a software in C++ environment to simulate it. Different network topologies with different traffic parameters were performed. The simulation results easily helped us to judge the merit of the proposed FM, FAQM and FS because of their remarkable performance over the traditional non-fuzzy mechanisms.     

Hierarchical Bucket Queuing for Fine‐Grained Priority Scheduling on the GPU

While the modern graphics processing unit (GPU) offers massive parallel compute power, the ability to influence the scheduling of these immense resources is severely limited. Therefore, the GPU is widely considered to be only suitable as an externally controlled co‐processor for homogeneous workloads which greatly restricts the potential applications of GPU computing. To address this issue, we present a new method to achieve fine‐grained priority scheduling on the GPU: hierarchical bucket queuing. By carefully distributing the workload among multiple queues and efficiently deciding which queue to draw work from next, we enable a variety of scheduling strategies. These strategies include fair‐scheduling, earliest‐deadline‐first scheduling and user‐defined dynamic priority scheduling. In a comparison with a sorting‐based approach, we reveal the advantages of hierarchical bucket queuing over previous work. Finally, we demonstrate the benefits of using priority scheduling in real‐world applications by example of path tracing and foveated micropolygon rendering.     

TinyOS中多优先级任务队列调度策略研究

针对TinyOS先来先服务调度策略中重要任务不能及时响应的不足,提出一种基于多优先级任务队列的调度策略。该调度策略将原来一个任务队列增加为三个优先级队列并引入抢占机制,最高优先级队列中的任务在满足抢占原则时才可以抢占其他队列正在执行的任务,任务只能在不同队列之间发生抢占,这样既减少了上下文切换,又保证了重要任务的优先执行。实验结果表明,该调度策略在不影响原有系统性能的情况下,提高了TinyOS对重要任务的响应性能。     

Medium-access control protocols for WDM-based optical access networks with passive-star clusters interconnected by a backbone ring

This paper investigates the performance of medium access control (MAC) protocols in a wavelength-division multiplexing (WDM) based optical access network consisting of a backbone ring interconnecting several passive-star-based clusters of optical networking units (ONUs) at customer premises. Each cluster is connected to the backbone through an access node (AN). A scheduler located in each AN, executes two MAC protocols, one for the intracluster traffic and the other for the intercluster traffic. In order to maintain the quality of service, the scheduler in the AN employs, priority-based queuing for the intercluster traffic on pre-assigned wavelengths. For controlling the intracluster traffic, the scheduler employs pre-transmission coordination with ranging and look-ahead functionalities in the MAC protocol. The performance of MAC protocol for intracluster traffic is evaluated through event-driven simulation, while for intercluster traffic the MAC performance is evaluated through analytical modeling of the queuing system employing two dynamic bandwidth management schemes. Performance of the intracluster MAC protocol is shown to be improved by novel use of subcarrier multiplexing on the wavelength used for the control packet transmission. A comparative study of the two intercluster schemes in terms of end-to-end delay is carried out, to understand the effect of priority queuing on the real-time and non-real-time service packets.     

Management of Multi-Queue Switches in QoS Networks

The concept of Quality of Service (QoS) networks has gained growing attention recently, as the traffic volume in the Internet constantly increases, and QoS guarantees are essential to ensure proper operation of most communication-based applications. A QoS switch serves m incoming queues by transmitting packets arriving to these queues through one output port, one packet per time step. Each packet is marked with a value indicating its priority in the network. Since the queues have bounded capacities and the rate of arriving packets can be much higher than the transmission rate, packets can be lost due to insufficient queue space. The goal is to maximize the total value of transmitted packets. This problem encapsulates two dependent questions: buffer management, namely which packets to admit into the queues, and scheduling, i.e. which queue to use for transmission in each time step. We use competitive analysis to study online switch performance in QoS-based networks. Specifically, we provide a novel generic technique that decouples the buffer management and scheduling problems. Our technique transforms any single-queue buffer management policy (preemptive or non-preemptive) to a scheduling and buffer management algorithm for our general m queues model, whose competitive ratio is at most twice the competitive ratio of the given buffer management policy. We use our technique to derive concrete algorithms for the general preemptive and non-preemptive cases, as well as for the interesting special cases of the 2-value model and the unit-value model. We also provide a 1.58-competitive randomized algorithm for the unit-value case. This case is interesting by itself since most current networks (e.g. IP networks) do not yet incorporate full QoS capabilities, and treat all packets equally.     

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