二进制堆排序算法的改进研究

基于对网络服务质量中队列调度算法的介绍和分析,从队列的优先级角度出发,对经典的二进制堆Heap调度排序算法进行了改进,提出了一种新的Heap＋算法,该算法充分利用原算法出队、入队操作数固定的特点,使其在保证硬件实现复杂度低的情况下能够做到出队、入队操作的流水化,从而达到高度的并行性。且具备很高的资源利用率和可扩展性,可用于高速链路上高精度虚拟时间的排序操作。     

支持优先级与公平策略的队列规程

首先介绍了队列调度算法在流量控制中的关键地位,然后讨论了现有队列调度算法,如基于优先级的调度算法、轮询调度算法与公平队列调度算法,最后提出了一种新的队列规程,该队列规程融合了优先级调度算法与DRR调度算法。在网络正常情况下,不同业务流公平地共享网络带宽,在网络出现拥塞的情况下,高优先级业务流能够抢占带宽,保证其较低的丢包率,并能够实现两种调度算法的快速切换。     

基于DynamipsGUI的网络服务质量实验设计

为了验证服务质量在解决网络带宽不足方面的作用，采用DynamipsGUI搭建网络环境，配置优先级队列，模拟了relnet以及大小为15000字节的数据从路由器转发时，路由器根据优先级队列将数据报文从不同队列转发的过程。实验表明，服务质量能够在一定程度上解决网络带宽不足的问题。     

多队列FIFO的设计及其在核心路由器中的应用

提供服务质量保证是目前Internet的重要研究课题之一,而在核心路由器上实现区分的服务质量保证则主要体现在对优先级队列的调度上。文章在分析QDR-SRAM操作时序的基础上,详细介绍了利用FPGA和QDR-SRAM实现多队列FIFO的设计方案,并讨论了通过利用该设计在核心级路由器中实现支持优先级调度的方案。在实际应用中,这种方案的硬件实现简单而且性能良好。     

一种带优先级队列的千兆以太网MAC设计

在以太网应用越来越广泛的背景下,针对某局域网具有传输数据量大和保持部分数据实时性的特点,采用了包含两种不同优先级帧的千兆以太网方案。基于Actel FPGA设计了一种带优先级队列的千兆全双工以太网MAC(Media access control),实现千兆以太网数据帧的收发,并对高优先级数据提供实时性支持。从分析含优先级字段的MAC帧结构着手,对MAC进行了模块划分,接着重点阐述了接收控制模块、发送控制模块和优先级队列模块。最后在ModelSim平台下对整个MAC进行了仿真验证;并使用Synplify进行了综合,结果表明GMII接口部分工作频率能达到141 MHz,内部模块工作频率能达到79 MHz,满足设计要求。     

无线网络中基于优先级队列延迟限定的研究

由于无线网络环境下网络节点的增加,网络延时成为一个亟待解决的问题。为了提高服务质量(QoS),提高吞吐量,文中提出了一种基于优先级的队列延迟模型,通过将每一个包预设置优先级来区分其重要性和实时性,同时将每一个AP设备中的队列根据优先级划分为3种类型,并将预设优先级的包放入其中进行传输,从而有效减少发送端的队列延迟。通过分析和仿真可以发现,与未划分优先级队列的节点网络相比,这种方案不仅使单个节点的延迟大幅减少,也使整个网络的平均延迟明显降低,网络整体性能显著提高。     

DiffServ中的队列管理机制

Diffserv可以实现三种服务：加速转发(EF)、确定转发(AF)和优先级服务(CS)，每种服务的PHB实现都采用了队列管理机制，文章对这三种服务的PHB队列管理机制进行了分析和研究。     

实现虚拟输出队列调度的神经网络方法

基于虚拟输出队列（VOQ）缓存的Crossbar交换结构,提出了一种Hopfield神经网络（HNN）控制的信元交换调度方法.通过选取合适的能量函数,并在其中采用一种新的队列优先级函数,实现了信元的高效交换控制.计算机模拟结果表明,该算法可以将吞吐率提高到0.998,信元丢失率大大降低,时延特性也有很大改善.     

一种低延迟的可扩展调度算法

提出了一种基于阈值的分布式迭代算法。与现有算法不同的是,该算法针对可扩展网络交换调度结构的特点,为处于最高优先级的调度器安排了2次迭代,第1次迭代用阈值方法找出一些较长的VOQ（虚拟输出队列）,并在最高优先级时隙之前的一个时隙完成,以缩短信号的处理时间。仿真结果表明,该算法与现有算法相比,在大流量的uniform流量模式下,延时性能和吞吐率获得了明显的提高。同时,该算法的硬件代价小,有效地实现了性能和复杂度的良好折中。     

区分服务模型中的一种动态队列管理算法

在对区分服务模型和RED算法进行分析的基础上，提出了一种基于RED算法的动态队列管理算法。实验结果证明，我们提出的算法在不损害高优先级数据流量的情况下，能较好地实时调整各优先级的门限值，减少网络资源的消耗，提高网络资源的利用率。     

Priority queue schedulers with approximate sorting inoutput-buffered switches

All recently proposed packet-scheduling algorithms for output-buffered switches that support quality-of-service (QoS) transmit packets in some priority order, e.g., according to deadlines, virtual finishing times, eligibility times, or other time stamps that are associated with a packet. Since maintaining a sorted priority queue introduces significant overhead, much emphasis on QoS scheduler design is put on methods to simplify the task of maintaining a priority queue. In this paper, we consider an approach that attempts to approximate a sorted priority queue at an output-buffered switch. The goal is to trade off less accurate sorting for lower computational overhead. Specifically, this paper presents a scheduler that approximates the sorted queue of an earliest-deadline-first (EDF) scheduler. The approximate scheduler is implemented using a set of prioritized first-in/first-out (FIFO) queues that are periodically relabeled. The scheduler can be efficiently implemented with a fixed number of pointer manipulations, thus enabling an implementation in hardware. Necessary and sufficient conditions for the worst-case delays of the scheduler with approximate sorting are presented. Numerical examples, including traces based on MPEG video, demonstrate that in realistic scenarios, scheduling with approximate sorting is a viable option     

Marker-based image segmentation relying on disjoint set union

Marker-based image segmentation has been widely used in image analysis and understanding. The well-known Meyer's marker-based watershed algorithm by immersion is realized using the hierarchical circular queues. A new marker-based segmentation algorithm relying on disjoint set union is proposed in this paper. It consists of three steps, namely: pixel sorting, set union, and pixel resolving. The memory requirement for the proposed algorithm is fixed as 2×N integers (N is the image size), whereas the memory requirement for Meyer's algorithm is image dependent. The advantage of the proposed algorithm lies at its regularity and simplicity in software/firmware/hardware implementation.     

A Novel Analytical Model for Switches With Shared Buffer

Switches with a shared buffer have lower packet loss probabilities than other types of switches when the sizes of the buffers are the same. In the past, the performance of shared buffer switches has been studied extensively. However, due to the strong dependencies of the output queues in the buffer, it is very difficult to find a good analytical model. Existing models are either accurate but have exponential complexities or not very accurate. In this paper, we propose a novel analytical model called the Aggregation model for switches with shared buffer. The model is based on the idea of induction: first find the behavior of two queues, then aggregate them into one block; then find the behavior of three queues while regarding two of the queues as one block, then aggregate the three queues into one block; then aggregate four queues, and so on. When all queues have been aggregated, the behavior of the entire switch will be found. This model has perfect accuracies under all tested conditions and has polynomial complexity.     

Waiting times in discrete-time cyclic-service systems

Single-served, multiqueue systems with cyclic service in discrete time are considered. Nonzero switchover times between consecutive queues are assumed; the service strategies at the various queues may differ. A decomposition for the amount of work in such systems is obtained, leading to an exact expression for a weighted sum of the mean waiting times at the various queues     

Optimization of fixed time polling schemes

This paper is concerned with the problem of deriving efficient operational rules for polling queues according to a fixed time polling scheme. A fixed time polling scheme specifies not only the visit order of the queues, but also the starting time for each visit. This problem arose from the need to efficiently collect files with call records from telecommunication switches. Using a simple approximation for the mean waiting times in a polling system with a non-cyclic visit order of the queues, we present an approach to the problem of minimizing a weighted sum of the mean waiting times at the various queues. This approach is tested via numerical experiments that are partly based on real network data.Part of O.J.B.'s research was supported by the European Grant BRA-QMIPS of CEC DG XIII.     

呼叫中心ACD模型的改进与实现

主要对目前呼叫中心自动呼叫分配（ACD）模型算法在实际应用中存在的问题进行分析,并针对问题提出相应的改进措施,具体表现为分别建立客户与座席队列,然后利用匹配算法对两队列进行匹配。本模型综合考虑了客户排队和座席分配方案,具有较强的灵活性和适应性,并在技术层面考虑话务员的技能水平,以实现从工作业绩上对话务员技能的激励,推动呼叫中心提升整体服务水平。     

The information-theoretic capacity of discrete-time queues

The information-theoretic capacity of continuous-time queues was analyzed recently by Anantharam and Verdu (see ibid. vol.42, p.4-18, 1996). Along similar lines, we analyze the information-theoretic capacity of two models of discrete-time queues. The first model has single packet arrivals and departures in a time slot and independent packet service times, and is the discrete-time analog of the continuous-time model analyzed by Anantharam and Verdu. We show that in this model, the geometric service time distribution plays a role analogous to that of the exponential distribution in continuous-time queues, in that, among all queues in this model with a given mean service time, the queue with geometric service time distribution has the least capacity. The second model allows multiple arrivals in each slot, and the queue is modeled as serving an independent random number of packets in each slot. We obtain upper and lower bounds on the capacity of queues with an arbitrary service distribution within this model, and show that the bounds coincide in the case of the queue that serves a geometrically distributed number of packets in each slot. We also discuss the extremal nature of the geometric service distribution within this model     

Approximate analysis of coupled queueing in ATM networks

We discuss a scheduling discipline for multiclass traffic in asynchronous transfer mode network nodes. The scheduler provides minimum bandwidth guarantees for each class of traffic and is well suited for high-speed implementation. The scheme is a modification of static head-of-line priority queueing, and was originally presented in a slightly different form by Huang and Wu (1993). We begin by considering a system with two queues which is analyzed by decoupling the system into separate M/G/1 queues. The analysis provides a very good estimate for the mean response time of customers in each queue. We also demonstrate the applicability of the analysis to a system with n⩾2 queues     

Dynamic server allocation to parallel queues with randomly varyingconnectivity

Consider N parallel queues competing for the attention of a single server. At each time slot each queue may be connected to the server or not depending on the value of a binary random variable, the connectivity variable. Allocation at each slot; is based on the connectivity information and on the lengths of the connected queues only. At the end of each slot, service may be completed with a given fixed probability. Such a queueing model is appropriate for some communication networks with changing topology. In the case of infinite buffers, necessary and sufficient conditions are obtained for stabilizability of the system in terms of the different system parameters. The allocation policy that serves the longest connected queue stabilizes the system when the stabilizability conditions hold. The same policy minimizes the delay for the special case of symmetric queues. In a system with a single buffer per queue, an allocation policy is obtained that maximizes the throughput and minimizes the delay when the arrival and service statistics of different queues are identical     

Performance evaluation of CSMA/ID MAC protocol for IP over WDM ring networks

In this paper, a packet pre‐classification media access control protocol based on a carrier sense multiple access with idle detection (CSMA/ID) scheme is investigated for supporting IP packets over all‐optical WDM ring networks. The purpose of the protocol is to increase throughput and to decrease the packet transmission delay of IP packets over optical networks in a metropolitan area network. This protocol avoids both packet collision and packet fragmentation. In order to improve the utilization of the network, the packets transmitted from a local area network are first pre‐classified into various class queues of an access point (AP) according to their length. After checking the available space based on the wavelength received by the receivers of the AP, the packets in the queues are transmitted. An analytical model is developed to evaluate the performance of the protocol, with simulation results showing good network efficiency. The proposed network has short‐term variations that introduce unfairness conditions. This problem could be overcome by assigning a quota on individual queues to allow all queues fair access. Copyright © 2008 John Wiley & Sons, Ltd.