The d-deap*: a fast and simple cache-aligned d-ary deap

This paper presents a generalized and cache-aligned implicit version of the deap, called d-deap* that utilizes cache memory efficiently. The d-deap* is based on a tree structure that may be mapped into a cache-aligned array without padding. This results in a match between node indexes and array indexes as well as good cache utilization. Experimental results show that the d-deap* clearly outperforms the symmetric min-max heap and deap structures proposed earlier for double-ended priority queues.     

Kinetic heap-ordered trees: Tight analysis and improved algorithms

The most natural kinetic data structure for maintaining the maximum of a collection of continuously changing numbers is the kinetic heap. Basch, Guibas, and Ramkumar proved that the maximum number of events processed by a kinetic heap with n numbers changing as linear functions of time is O(nlog²n) and . We prove that this number is actually Θ(nlogn). In the kinetic heap, a linear number of events are stored in a priority queue, consequently, it takes O(logn) time to determine the next event at each iteration. We also present a modified version of the kinetic heap that processes O(nlogn/loglogn) events, with the same O(logn) time complexity to determine the next event.     

Kinetic Collision Detection for Convex Fat Objects

We design compact and responsive kinetic data structures for detecting collisions between n convex fat objects in 3-dimensional space that can have arbitrary sizes. Our main results are:

基于拓扑约束模板的支吊架建模方法研究

基于支吊架标准和形式的分析,抽象出了支吊架拓扑结构的层次模型,提出了基于对偶智能点的支吊架拓扑约束模型,解决了支吊架拓扑关系多元性和层次性导致的智能组嵌套问题。使用拓扑约束模板表达支吊架设计标准,将支吊架设计转化为多元约束求解,解决了支吊架设计中设计标准的多样性和专业间的紧密协同性两个关键性问题。     

服装吊挂系统上位机软件设计与实现

介绍了一种基于以太网和RS485总线的服装吊挂系统设计,阐述了该系统的上位机软件的设计与实现。上位机软件是系统的控制中心,监控管理每个工作站的生产状况,实时生成薪资报表、产量报表、生产分析图。软件界面采用C#编程语言,通信模块的程序采用Delphi技术实现,后台数据库采用SQL2000。该系统已经投入企业使用,系统各项功能运行稳定,界面友好,满足用户需求。     

支持服务优先级的多阶段服务模型研究

多阶段服务模型是一种支持高并发、高吞吐的事件驱动服务应用架构,为使其更好地适应当前Internet上大部分应用提供区分等级服务的现状,提出了一种为该模型增加对带优先级请求支持的方法;定义了动态优先级,改进了随机早期检测算法以控制不同优先级事件的入队,并通过优先级动态提升防止低优先级事件被“饿死”。实验结果表明,改进后的模型在保持系统良好性能的基础上,满足了不同优先级请求的实时性和吞吐率需求。     

线程池技术在B/S 网络管理软件架构中的应用

针对网络管理软件后台存在应用服务器的数据处理量多和资源消耗过大的问题,提出了改进算法,研究了线程池技术,包括线程池的工作原理、线程池使用方式、线程池配置方法、线程池监控方法和线程池的关闭方法。线程池根据基本线程池、工作队列和整个线程池的饱和情况进行工作,依据任务性质、任务优先级、任务执行时间和任务依赖性进行线程配置,以达到高效执行和最优资源的利用。     

Analysis of a nonpreemptive priority queue with SPP arrivals of high class

This paper considers a nonpreemptive priority queueing system with two priority classes of customers, where high priority customers arrive to the system in accordance with a switched Poisson process (SPP) and low priority customers in accordance with a Poisson process. Using the supplementary variable technique, we derive the joint probability generating function of the stationary queue length distributions and the Laplace-Stieltjes transforms of the stationary waiting time distributions of high and low priority customers. We also present some numerical results in order to show the computational feasibility of the analytical results.     

支持QoS的IEEE 802.11的分布协调功能(DCF)算法

IEEE802．11是一种无线局域网标准，它采用CSMA／CA算法，有两种工作模式——DCF和PCF。当无线站点工作于DCF模式时，可以方便地构建自组网络.DCF模式是一种随机的无线信道共享方式，不能保障语音、视频等实时业务。本文按照各种业务的服务需求，在DCF中引入并行优先级队列，使这些队列接入信道的参数DIFS和CW与各种类型应用相对应，从而在MAC层中实现服务区分。     

IP报文优先级分配的一种方案

IP路由器在处理到达的报文时可有多种排队方式犤1,2犦。文章提出的将用户数据报类型及报文长度综合考虑的多级优先多队列方案,可改善该排队系统的平均时延,而保持原有的QoS。文章同时给出方案的报文平均等待时间的绝对与相对的数量分析。对于报文长度与优先级的关系问题,以往典型的提法是“短报文应优先,以免被长报文拖延”犤5犦,这种提法有其片面性。实际上,短报文应优先,以改善排队系统的系统平均时延;而如果按报文长度赋予优先级,短报文优先,则可达到最佳系统平均时延。     

PbRED:基于优先级的RED改进算法

随机早期检测算法RED作为一种重要的主动队列管理算法,通过有效地控制队列长度,取得较好的吞吐量性能。然而,当多个业务流存在不同优先级时,不能很好地区分服务质量。提出一种新的RED改进算法—PbRED,基于业务的优先级调整丢弃概率,通过减小高优先级的丢弃概率、增大低优先级的丢弃概率,为不同优先级的业务进行区分服务。仿真实验结果表明,在获得较高吞吐量的同时,PbRED可以使不同优先级业务流的服务质量存在合理区分度,保证高优先级业务流获得更好的吞吐量性能。     

基于时延的动态优先级调度算法

队列管理是提高网络QoS的一种有效方法。在基于时延的调度算法（BDS）基础上将时间片与优先级相结合,提出了一种基于时延的动态优先级调度算法（DDPQS）。为了实现该算法,针对进入缓冲区的每个子队列设置一个计数器,以调整的计数器值为基准来动态的改变队列的优先级,从而达到队列调度的效果;又从研究该算法的过程中,发现其局限性,即计数器值对时间片过于敏感的问题,于是进一步采用设置阈值进行区分的方法来优化。优化前后的仿真结果表明,时延和吞吐率性能具有明显改善。     

Two new methods for constructing double-ended priority queues from priority queues

We introduce two data-structural transformations to construct double-ended priority queues from priority queues. To apply our transformations the priority queues exploited must support the extraction of an unspecified element, in addition to the standard priority-queue operations. With the first transformation we obtain a double-ended priority queue which guarantees the worst-case cost of O(1) for find-min, find-max, insert, extract; and the worst-case cost of O(lg n) with at most lg n + O(1) element comparisons for delete. With the second transformation we get a meldable double-ended priority queue which guarantees the worst-case cost of O(1) for find-min, find-max, insert, extract; the worst-case cost of O(lg n) with at most lg n + O(lg lg n) element comparisons for delete; and the worst-case cost of O(min {lg m, lg n}) for meld. Here, m and n denote the number of elements stored in the data structures prior to the operation in question. The work of the authors was partially supported by the Danish Natural Science Research Council under contracts 21-02-0501 (project Practical data structures and algorithms) and 272-05-0272 (project Generic programming—algorithms and tools). A. Elmasry was supported by Alexander von Humboldt fellowship.     

DiffServ模型中主动队列管理研究

区分服务模型是现代大规模网络保证IP QoS的主要模型,该模型是当前互联网通讯性能方面研究的热点问题。在改进RIO-C算法的基础上,提出了一种适合于区分服务模型的主动队列管理算法-PFRIO（RIO based on Priority and Fair）。该算法提高了带宽分配的公平性,增强了网络对突发数据流的处理能力,有效改善了区分服务模型的总体性能。     

基于优先队列的时变网络最短路径算法

提出了基于优先队列的时变网络最短路径算法,能克服传统最短路径算法难以对时变网络求解最短路径的缺陷。提出的时间窗选择策略能够在算法求解过程中为节点选择合适的时间窗以降低路径长度,从而求得精确解。进一步地,算法使用了优先队列组织节点集合以提高计算效率。在随机生成的网络数据以及美国道路数据上的实验表明,基于优先队列的时变网络最短路径算法与经典方法相比,不仅能够求得精确解,运算速度也有所提高。     

9PQS：MANET中一种有效的队列调度机制

提出一种针对移动自组网的动态优先权队列调度机制（Dynamic Priority Queue Scheduling，DPQS）。为缓冲区设置最大、最小两个阈值，将其分为三个不同的负载阶段，然后根据当前缓冲区的负载情况动态调整各种类型数据包的优先等级，从而在不影响快速建立路由的前提下，降低数据包在网络中的传输延时，提高网络的性能。仿真结果表明DPQS机制有效地降低了网络传输延时，并对网络的吞吐量也有一定的提高。     

DPQS:MANET中一种有效的队列调度机制

提出一种针对移动自组网的动态优先权队列调度机制(DynamicPriorityQueueScheduling,DPQS)。为缓冲区设置最大、最小两个阈值,将其分为三个不同的负载阶段,然后根据当前缓冲区的负载情况动态调整各种类型数据包的优先等级,从而在不影响快速建立路由的前提下,降低数据包在网络中的传输延时,提高网络的性能。仿真结果表明DPQS机制有效地降低了网络传输延时,并对网络的吞吐量也有一定的提高。