端到端时间约束的实时任务动态调度算法

在单处理机系统中,由于计算高优先级任务抢占的时间相对比较简单,所以单处理机调度理论取得了长足的进步.提出一个端到端时间约束的实时任务调度算法,当实时任务到达系统时,算法为任务的每个子任务在相应的处理机上预约一定的计算资源,把端到端的多处理机调度问题转换成单处理机调度问题,从而可以利用单处理机调度理论判定实时任务的可调度性.实验表明,该算法明显地提高了CPU利用率和任务接收率.     

分布式调度算法在VOQ交换机中的应用

为提高高速通信网络的通信效率，针对VOQ交换机，提出在交换机的各个输出端口中进行分布式通信调度(DSA)的策略。DSA算法可直接支持变长数据包通信调度，克服了传统信元交换只能调度定长数据包的缺点，降低了交换机的实现复杂度。仿真结果表明：在各种流量下，DSA算法都比信元调度算法具有更好的调度性能。     

面向控制网络的交换机调度机制研究

针对基于虚拟输出排队的输入队列交换机应用于控制网络所存在的诸多困难,提出了一种新的输入队列交换机结构,并根据新的结构设计了一种基于记录矩阵和需求矩阵的信元传输川页序控制方案,以解决交换机中存在的信元行为及时延的不确定性问题。交换机采用两级调度机制,链接调度提供分级服务,交换调度实现端口匹配,以适应控制网络的流量特征。     

一种基于输入队列的交换机快速会聚调度算法

随着网络带宽需求的增加,高性能交换机的地位日趋重要。交换机包括3个部分:(1)在输入端口保存到达此端口的信元的输入缓冲。(2)在输出端口保存将要发送的信元的输出缓冲。(3)调度输入信元到所需输出端口的调度模块。当由多个输入端口要求输出到同一输出端口的时候由此调度算法来裁决一个输入输出对。一般而言,交换机的性能很大一部分取决于这一调度算法的性能,但并不希望这一调度算法成为交换机性能的瓶颈。该文讨论了许多近年来常用的算法,在此基础上同时提出一种新的的调度算法。通过计算机模拟结果可以看出这种算法具有更高的效率,更快的会聚速度。     

支持区分服务的自适应队列调度管理

队列调度是网络中间节点（路由器和交换机）用来支持不同的服务质量所采用的关键机制之一。讨论了DiffServ模型下的WRR算法和DWRR算法，并在DWRR基础上提出一种针对实时多媒体业务的调度算法（ADWRR），同时描述了该算法的实现过程。该算法根据各队列的延迟指数（DI）来动态调整队列的调度次序。AWDRR算法能够降低实时多媒体业务的端对端时延和传输时延抖动，能为实时多媒体业务提供更好的QoS保证。     

现场级硬实时网络在线调度

通过对主要周期和非周期硬实时调度算法的深入研究，提出了一种可用于调度链路数据包的在线硬实时调度系统(ARTCS)。该调度器基于单调比率调度算法：RM、风车调度算法Sr和轮询服务器调度算法，能快速判定可调度性，进而自动生成总线表，使调度算法将数据包作为周期数据包进行调度。ARTCS简单、易用，有效地利用了总线带宽。顺序执行总线表，不仅能保证硬实时的性能，而且避免了消息传输中的中断和阻塞，因而较好地满足了现场总线领域中硬实时通信系统的要求。     

AFDX交换机的队列整形调度研究

AFDX交换机的静态优先级非抢占式队列调度(SPUS)算法不能消除输出分组中的随机抖动。为此,采用将虚拟时钟作为分组调度发放合法时间的方法对SPUS算法进行改进。在发往级联端口的分组输出之前,先经过整形调度使数据流均匀地输出,以确保交换机的服务质量。仿真结果表明,改进后的算法可消除输出分组随机抖动,适用于交换机级联端口。     

基于多片FPGA的双优先级动态调度算法

针对单片现场可编程门阵列(FPGA)在处理高速网络中海量数据时存在效率低下的问题,结合多处理器的双优先级调度算法,在所构建的多片FPGA并行处理的高速数据采集和处理模型上,提出一种基于多片FPGA的双优先级动态调度算法,并对处于低优先级段的强实时周期任务提出一种最早截止期临界松弛调度(EDCL)算法。根据任务的松弛度确定任务的优先级,若提升时间到达时仍未完成,则将其提升到高优先级段; 对软实时周期任务,设置在中优先级段,通过延长当前任务截止期至动态模糊阈值进行调度。实验结果表明,该算法能很好地调度强实时周期任务,保证重要任务的优先执行,并能降低由于抢占造成的软实时周期任务错失率。     

基于时槽预定的加权公平调度策略

面向以太网的物理帧时槽交换(Ethernet-oriented physical frame timeslot switching,简称EPFTS)技术以用户域内使用最为广泛的以太网MAC(media access control)帧为运载对象、以定长物理层帧EPF(Ethernet-oriented physical frame)的传输时间为时槽,作为数据传输与交换的基础.针对EPFTS交换技术的特点,提出了一类新的调度策略--时槽加权的公平调度原则(timeslot-reservation based weighted fair scheduling,简称TRWFS),以解决EPFTS交换机中的业务数据调度问题.TRWFS以连接建立阶段各业务流预定的时槽数为基础,控制交换矩阵仲裁过程中各输入端向输出端请求转发信元的时刻,借用一般轮询算法的二相迭代机制来解决端口冲突问题.还给出了TRWFS的3种实现算法,表明TRWFS的实现复杂度可与一般Round-Robin调度算法相当.仿真实验结果进一步表明,即使在重负载条件下,TRWFS仍可有效保障EPFTS交换机各端口对上的预定时槽数,并在平均传输时延和吞吐率保障方面优于其他经典调度算法.     

FC交换机中优先级技术的研究和实现

针对光纤通道（FC）交换机,研究并设计了一种三级优先级实施策略,保证高优先级数据以最快的速度从交换机调度输出。重点对输入端口VOQ机制、Crossbar分布式调度和输出端口控制等关键技术进行了描述,并基于Xilinx平台对交换机优先级的有效性进行了验证。验证结果表明,该策略满足FC交换机优先级调度要求。所做的研究为自主化FC交换机产品的研制奠定了有效的基础,也对采用FPGA实现各种网络协议具有积极的借鉴意义。     

主从结构交换式以太网中实时消息调度研究

为使交换式以太网能满足实时通信的要求,针对FTT SE网络调度模型,提出了一种同时适用于周期性和非周期性实时消息的链路可调度性判定方法。在证明了消息链路调度优化问题MLSOP为NP complete的同时,针对周期性实时消息的链路调度优化给出了启发式算法LSHA。最后,对于周期性和非周期性实时消息分别设计了基于EDF的调度算法。仿真实验表明,在提高网络链路带宽利用率和减小消息平均延时方面,该算法均较FTT SE有明显的优势。     

交换以太网中实时消息截止期划分算法研究

为解决交换式以太网中实时消息在发送及接收链路上的截止期划分问题,首先给出了非抢占式EDF调度算法的可调度性分析方法,并分析了消息的提前释放对非抢占式EDF调度算法可调度性的影响,在此基础上提出了新的截止期划分算法(MDPS)。算法通过计算可满足调度条件时消息在发送链路及接收链路截止期应该划分的下限,并结合截止期的松驰量实现实时消息在发送及接收链路上的截止期划分。算法实验比较和分析表明,该算法在提高网络聚合带宽、减小消息的错失率方面明显优于现有的ADPS算法。     

COTS Switch工业以太网实时调度算法

针对基于商用现成组件技术（Commercial Off-The-Shelf,COTS）的交换式以太网不能满足工业数据通信的实时性要求问题,给出了改进的FTT（Flexible Time-Triggered communication paradigm）网络调度模型,提出了新的周期性实时消息链路可调度性优化判定方法,在此基础上设计了一种基于EDF（Earliest Deadline First）的实时调度算法。算法通过对网络消息流量进行有效控制防止交换机缓冲区溢出,同时充分发挥网络在同一时间存在多个并行传输链路的优势,提高了网络实时性。仿真实验表明该算法在提高网络的聚合带宽、减小消息的平均等待延时和丢失率方面均有明显的优势。     

Adaptive scheduling for integrated traffic on WDM optical networks

One of the important issues in the design of future generation of high-speed networks is to provide differentiated service to different types of traffic with various time constraints. In this paper, we study the problem of providing real-time service to either hard or soft real-time messages and normal transmission service to variable-length messages without time constraints in WDM optical networks. We propose an adaptive scheduling algorithm for scheduling message transmissions in order to improve the network performance when both real-time and non real-time messages are transmitted in one topology. We have analyzed the complexity of the algorithm to show its feasibility. We have conducted extensive discrete-event simulations to evaluate the performance of the proposed algorithm. The study suggests that when scheduling message transmission in WDM networks differentiated services should be considered in order to meet time constraints of real-time messages while non real-time messages are being served so that the overall performance of the network could be improved.     

EDF调度算法在COTS交换式工业以太网上的实现

将交换式以太网引入工业实时通信领域正受到越来越多的关注,但是,基于成熟商用组件技术（COTS）的交换式以太网在实时性方面的缺陷限制了其在工业实时通信领域中应用。基于FTT模型（Flexible Time—Triggered communication paradigm）,在无须对现有交换以太网做任何硬件改动的前提下,实现了交换式以太网上周期性实时消息与其它消息在时间上严格隔离,并针对周期性实时消息传输提出了一种基于EDF的实时性调度算法,仿真实验表明该算法具有明显的优点。     

Applications of machine learning approach on multi-queue message scheduling

Due to limited resource contentions and deadline constraints, messages on the controller area network (CAN) are competing for service from the common resources. This problem can be resolved by assigning priorities to different message classes to satisfy time-critical applications. Actually, because of the fluctuation of network traffic or an inefficient use of resources, these static or dynamic priority policies may not guarantee flexibility for different kinds of messages in real-time scheduling. Consequently, the message transmission which cannot comply with the timing requirements or deadlines may deteriorate system performance significantly. In this paper, we have proposed a controller-plant model, where the plant is analogous to a message queue pool (MQP) and the message scheduling controller (MSC) is responsible to dispatch resources for queued messages according to the feedback information from the MQP. The message scheduling controller, which is realized by the radial basis function (RBF) network, is designed with machine learning algorithm to compensate the variations in plant dynamics. The MSC with the novel hybrid learning schemes can ensure a low and stable message waiting time variance (or a uniform distribution of waiting time) and lower transmission failures. A significant emphasis of the MSC is the variable structure of the RBF model to accommodate to complex scheduling situations. Simulation experiments have shown that several variants of the MSC significantly improve overall system performance over the static scheduling strategies and the dynamic earliest-deadline first (EDF) algorithms under a wide range of workload characteristics and execution environments.     

CAN报文实时性分析及在线评估

结合CAN总线的位填充机制和最坏情况下的报文延迟时间的数学模型，针对周期性报文,提出基于主节点的报文调度方式，给出了该调度方式下的报文响应时间数学模型．通过CAN总线系统实验平台,对CAN报文的实际长度进行检测和分析，并对符合SAE标准的报文实时性进行了分析和评估．实验表明，基于主节点的调度方式保证了CAN报文的实时性，使得系统具有可调度性．     

A Message Scheduling Scheme for All-to-All Personalized Communication on Ethernet Switched Clusters

We develop a message scheduling scheme for efficiently realizing all-to-all personalized communication (AAPC) on Ethernet switched clusters with one or more switches. To avoid network contention and achieve high performance, the message scheduling scheme partitions AAPC into phases such that 1) there is no network contention within each phase and 2) the number of phases is minimum. Thus, realizing AAPC with the contention-free phases computed by the message scheduling algorithm can potentially achieve the minimum communication completion time. In practice, phased AAPC schemes must introduce synchronizations to separate messages in different phases. We investigate various synchronization mechanisms and various methods for incorporating synchronizations into the AAPC phases. Experimental results show that the message scheduling-based AAPC implementations with proper synchronization consistently achieve high performance on clusters with many different network topologies when the message size is large     

Scheduling time-constrained multicast messages in circuit-switched tree networks

In this paper, we consider a kind of multicast scheduling problem in a tree network. Each multicast message is transmitted through a directed subtree within the tree network. The transmission time of each multicast message is assumed to be one unit. Two messages can be transmitted at the same time if their subtrees are edge-disjoint. Each message is constrained by a ready time and a deadline, and has a weight we can gain if it is scheduled within its deadline. The optimality criterion is the total weight we gain. We assume that the degree of each subtree is bounded by a constant d and present an approximation algorithm of which the approximation ratio is at most 4d+15.     

实时以太网控制系统的功能块执行方法

为了提高实时以太网控制系统的运行效率和通信性能,在EPA（Ethernet for Plant Automation）确定性通信调度的基础上提出了一种功能块执行方法。该方法将现场设备中所有需要远程通信的功能块整合为功能任务,并且按照功能块执行与数据通信周期同步的原理确定了功能任务的执行规律：功能任务在单个通信宏周期中只能单次执行,当周期报文空窗期满足功能任务执行需求时,功能任务在周期报文传输任务结束时执行;当周期报文空窗期不能满足功能任务执行需求时,功能任务在非周期报文传输任务结束时执行。实验证明,该方法实现了系统中功能任务与通信任务的周期同步,避免了功能块的无效执行与数据的无效传输,提高了系统的运行效率和通信性能。