An Innovative Solution for Dynamic Bandwidth Engineering in IP/MPLS Networks with QoS Support

This paper reports an original module for effectively handling bandwidth resources in a multi-service MPLS network. This module, named bandwidth engineering, allows accommodating more traffic with respect to traditional IP networks, reducing the network blocking probability, while preserving Class of Service (CoS) requirements. It consists of an algorithm that handles priority between label switched paths associated to different classes of services, and of a dynamic routing algorithm that works with the bandwidth constraint. Simulation results are reported to assess the validity of the proposed solution.     

Research on run-time overhead of RM and improvement

The rate-monotonic (RM) algorithm is a classic fixed priority real-time scheduling algorithm. However, in most embedded real-time systems where the workload is composed of many tasks of high frequency and short execution time, the overheads from preemptions of the real-time operating system will lead to a low resource utilization rate if the RM algorithm is directly used. By studying the preemption relationship of the tasks scheduled by RM algorithm, a model of preemption overheads is established with task attributes, based on which the run-time preemption overheads of RM algorithm are reduced by optimizing the start time of the tasks in embedded real-time systems. Finally, the experimental results show the validity of the proposed strategy. __________ Translated from Journal on Communications, 2008, 29(2): 79–86 [译自: 通信学报]     

有中断时间代价的一致并行机抢先调度问题

提出了一种具有中断时间代价的抢先调度问题(P|ptmn(δ)|C_max):在抢先调度中,一个任务发生一次中断,其总的执行时间会增加一个δ.该问题在工程任务分配、分布式计算和网络通信等实际问题中有着广泛的应用背景.证明了这是一个NP-hard问题,给出了一个时间复杂度为O(nlogn+m)的脱线近似算法LPT-Wrap,其近似比小于等于1.40825,并分析了P|ptmn(δ)|C_max的在线特性,给出一个线性时间复杂度的在线近似算法,其竞争比为2.     

DS-TE网络环境中的抢占算法

针对V-PREPT（Versatile Preemption）算法因只关心最小化抢占总代价,不考虑被抢占标记交换路径的规模而引起重路由开销极大增加的问题,提出了改进算法——N-PREPT。该算法在最小化抢占总代价的前提下,根据参数设置的不同分别对标记交换路径进行抢占。将最小化抢占路径数目、避免发生级联抢占的优化标准置于首位,通过采用层层逼近规则提高对抢占数目的约束程度。实验结果表明,当网络中发生抢占时,改进算法在减少重路由开销方面的性能优于V—PREPT算法,提高了网络资源的利用率和网络的QoS（Quality of Service）保障能力。     

改进的基于抢占阈值调度的任务响应时间分析方法

基于抢占阈值调度的任务响应时间分析方法是一种新型实时系统任务可调度性判定技术。然而已有的研究工作,有时对以前的任务请求检查过少,可能导致对响应时间估计过低。同时对任务响应时间的分析忽略了任务释放抖动和时钟嘀嗒调度对任务响应时间的影响,造成任务错过期限的现象,系统任务可调度性判定存在潜在的不精确因素。针对上述缺点不足,本文提出改进的基于抢占阈值调度的任务响应时间分析方法,在修正已有方法缺陷的同时,考虑任务释放抖动和时钟嘀嗒调度的影响,引入额外的时间需求,使用改进的任务参数计算系统任务时间需求函数。仿真对比结果表明,改进后的方法较单纯固定优先级抢占阈值调度下的任务响应时间分析方法得到更加精确可调度性分析结果。     

嵌入式Linux实时化方法研究

通过分析Linux调度策略,指出Linux实时性方面的不足.从Linux内部改造和外部实时扩展方面研究了Linux实时化方法.内部改造包括:时钟机制改造和内核抢占性改造.外部实时扩展主要是采用双内核.     

改善Linux内核实时性方法的研究与实现

针对开放源码的Linux内核,在参考了其实时性相关研究的基础上,提出了改进其实时性能的2个措施：中断线程化和改进自旋锁机制,并在最新的标准Linux2.6内核上加以实现.经测试,改进后的内核具有更短的中断延迟和任务抢占延迟,实时性能得到了很大的提高.     

嵌入式实时操作系统分析

实时多任务操作系统（RTOS）是嵌入式应用软件的基础和开发平台。在从功能、性能模型等角度对实时操作系统进行分析的基础上,描述了抢占式任务调度和中断禁止时间与中断延迟事件的实现。对Linux的系统调用功能的分析,是研究Linux内核源码几个很好的入口点之一。     

在构件化嵌入式操作系统中应用抢占阈值调度

现有基于构件的嵌入式实时软件开发过程着重于从结构的角度分解系统成若干构件,以及重用构件。实践证明,该开发过程还应从运行角度将构件映射成任务,并选择适当的实时调度算法。为此,根据目前的工程实践提出一种实时构件模型,包含将构件映射成任务的方式。描述了当前构件化嵌入式操作系统可以使用的4种调度算法,并比较这些算法的性能特点。提出抢占阈值(preemptionthreshold)调度模型更适合构件化嵌入式实时系统,仿真实验的结果证明了该结论。比较结果和结论对构件化嵌入式实时系统的设计和开发有一定的参考价值。     

DiffServ/MPLS网络中最小化抢占的路由算法

在支持具有不同优先级和不同QoS需求的多业务网络中,抢占是带宽分配和管理的有效策略,但同时也对网络造成了振荡。在路径选择策略中引入抢占信息可最小化重路由,提高网络的稳定性。论文给出了最小化抢占的路由问题的数学规划模型。在此基础上提出了简单的启发式算法以运用于大型实际网络。策略是将路径选择和连接建立过程有效地结合起来,对现有的MPLS信令协议仅做了少许扩展。仿真证明该算法能达到抢占最小化的优化目标,有效地提高网络性能。