Semi-Markov decision models for real-time scheduling

We first present a class of real-time scheduling problems and show that these can be formulated as semi-Markov decision problems. Then we discuss two practical difficulties in solving such problems. The first is that the resulting model requires a large amount of data that is difficult to obtain; the second is that the resulting model usually has a state space that is too large for analytic consideration. Finally, we present a non-intrusive ‘knowledge acquisition’ method that identifies the states and transition probabilities that an expert uses in solving these problems. This information is then used in the semi-Markov optimization problem. A circuit board production line is used to demonstrate the feasibility of this method. The size of the state space is reduced from 2035 states to 308 by an empirical procedure. An ‘optimal’ solution is derived based on the model with the reduced state space and estimated transition probabilities. The resulting schedule is significantly better than the one used by the observed expert.     

A pinwheel packet scheduling scheme for broadband wireless networks

Abstract

A frame‐based packet scheduling scheme, the pinwheel scheduling (PWS) scheme, is proposed and investigated at the medium access control (MAC) layer in broadband wireless networks. The objective of the proposed scheduling scheme is to provide low delay and low jitter for real‐time traffic. We have demonstrated in this paper that the proposed PWS scheme not only satisfies the packet‐level QoS requirements but also has low implementation cost. The PWS scheme gives the highest priority to CBR connections in a service cycle to minimize their delay and jitter. For ABR traffic, a number of slots are allocated to fit their MCR. The remaining time slots are then allocated to VBR traffic according to their PCR. Thus, the VBR traffic may suffer large delay and jitter when the number of CBR connections increases. The PWS with modular strategy (PWS/MS) is proposed to improve the performance of the VBR traffic. We also introduce three different slot‐reuse strategies named real‐time traffic first (RTF), non‐real‐time traffic first (NRTF) and longest queue first (LQF), respectively, to improve resource utilization. In order to demonstrate the performance of the PWS and PWS/MS schemes, comparisons are made with existing schemes such as the round‐robin (RR) and weighted‐round‐robin (WRR) by using OPNET software. Simulation results show that the proposed schemes are capable of maintaining the lowest delay and jitter for VBR and CBR traffic while not sacrificing the available bit rate (ABR) traffic.     

Ground resource optimization for navigation constellation based on satellite link scheduling

The Global Navigation Satellite System (GNSS) provides autonomous geospatial positioning and time synchronization services for civilian and military purposes. GNSS satellite links are used to transmit signals for constellation management and other applications. To minimize the number of stations required in participant ground-based management and reduce management costs in the GNSS network, this study solves the satellite link scheduling problem over the dynamic satellite network, including the hybrid and fast-varying inter-satellite link (ISL) working system. Firstly, the management problem is divided into two phases. Secondly, a two-level solving scheme is designed according to the characteristics of the scheduling problem. Finally, a performance analysis of different scenarios is conducted. The experimental results show that the hybrid ISL working system provides more effectively utilized data transmitting bandwidth of satellite links, thereby reducing the use of ground-based management resources. This study provides a technical reference for the management of future large-scale satellite networks.     

Multi-rate power-controlled link scheduling for mesh broadband wireless access networks

The problem of multi-rate power-controlled collision-free scheduling in spatial time division multiple access (STDMA) wireless mesh networks is formulated as a mathematical program utilising cross layer information. As these mixed integer linear programs are intractable (NP-hard problems), optimal collision-free schedules can be found only for topologies consisting of a few nodes. To this end, approximation algorithms that are based on linear programming relaxation and randomised rounding are studied. The proposed framework, which aims to maximise the spatial timeslot reuse under predefined signal-to-interference noise ratio thresholds, is suitable for providing centralised scheduling in the mesh mode of the IEEE 802.16 standard. Performance aspects of the approximation algorithms under different scenarios are investigated.     

Securing ARP and DHCP for mitigating link layer attacks

Network security has become a concern with the rapid growth and expansion of the Internet. While there are several ways to provide security for communications at the application, transport, or network layers, the data link layer security has not yet been adequately addressed. Dynamic Host Configuration Protocol (DHCP) and Address Resolution Protocol (ARP) are link layer protocols that are essential for network operation. They were designed without any security features. Therefore, they are vulnerable to a number of attacks such as the rogue DHCP server, DHCP starvation, host impersonation, man-in-the-middle, and denial of service attacks. Vulnerabilities in ARP and DHCP threaten the operation of any network. The existing solutions to secure ARP and DHCP could not mitigate DHCP starvation and host impersonation attacks. This work introduces a new solution to secure ARP and DHCP for preventing and mitigating these LAN attacks. The proposed solution provides integrity and authenticity for ARP and DHCP messages. Security properties and performance of the proposed schemes are investigated and compared to other related schemes.     

基于统计性QoS保证的数据包延时界调度算法

讨论了调度算法的性能指标，对目前基于业务流的调度算法的技术特点与性能优劣进行了分析和比较．重点研究了基于时延和丢包率的算法，并提出了一种基于数据包延时界（PDB）排列的调度策略，与WFQ及传统EDF算法进行了比较，证明业务端到端超时概率随网络带宽利用率的变化性能优于传统EDF算法．     

水声通信网数据链路层协议仿真研究

简要介绍了水声通信网的研究现状和水声网络组网方式,提出一种比较适合于浅海的水声通信网数据链路层协议,并在NS2仿真器上进行了仿真研究。仿真结果表明,该协议在浅海声信道环境中具有一定的适用性,在低负荷情况下,此协议可以满足系统的要求。满负荷时网络的吞吐量出现降低的现象需进一步改进。     

Combined methodology for measurement of available bandwidth and link capacity in wired packet networks

Accurate measurement of network parameters such as available bandwidth (ABW), link capacity, delay, packet loss and jitter are used to support and monitor several network functions, for example traffic engineering, quality-of-service (QoS) routing, end-to-end transport performance optimisation and link capacity planning. However, proactive network measurement schemes can impact both the data traffic and the measurement process itself, affecting the accuracy of the estimation if a significant amount of probe traffic is injected into the network. In this work, the authors propose two measurement schemes, one for measuring ABW and the other for measuring link capacity, both of them use a combination of data probe packets and Internet control messaging protocol (ICMP) packets. Our schemes perform ABW and link-capacity measurements in a short time and with a small amount of probe traffic. The authors show a performance study of our measurement schemes and compare their accuracy to those of other existing measurement schemes and also show that the proposed schemes achieve shorter convergence time than other existing schemes and high accuracy.     

A real-time scheduling method for the cluster tool with wafer transfer delay

In this study, we propose an effective real-time scheduling method based on the timetabling technique for the cluster tool. Instead of considering the no-wait assumption generally adopted in almost all of the previous literature, we take wafer transfer delay into consideration, which implies that a wafer can stay at the current chamber for a certain, limited time before proceeding to the next chamber. In order to improve the total cycle time, an additional pulling procedure to the timetabling is introduced and applied. Numerical examples show that the proposed method gives effective schedules in real time even for practical-sized problems.     

Mesh模式下基于最小干扰流量的带宽调度算法

研究了干扰链路流量大小对IEEE802．16Mesh网络传输性能的影响,提出了一种通过计算用户站（SS）和基站（BS）的通信路径干扰的总流量来寻找总干扰流量最小的路由算法,并结合路由树给出了一种冲突避免调度的方法。该算法既考虑了干扰链路的数量,又考虑了干扰链路的实际通信强度,在建立路由树的过程中能够更快地使系统达到更佳的负载均衡状态,最大强度地避免调度中可能出现的带宽冲突。由于干扰流量的影响可以得到有效的控制,系统的吞吐量可以明显提高。仿真结果验证了该算法的有效性。     

基于服务曲线的TDMA无线网络上行信道时隙调度算法

研究了采用TDMA接入方式的无线分组网络上行信道时隙分配策略,基于移动台的QoS要求,提出了一种自适应时隙分配算法。利用服务曲线对移动台的QoS要求进行了建模。算法的目标是在尽量满足所有移动台Qos要求的基础上提高系统的上行吞吐量。在无法满足所有移动台QoS要求的情况下,使得移动台实际发送的数据与满足服务曲线要求之间的偏差最小。仿真结果表明：该算法能够在系统吞吐量和系统偏差之间进行折衷,从而有效地平衡上述两个目标。     

一种多源协作网络中轮询节点选择算法

针对放大转发(AF)的多源多中继两跳协作通信网络模型,提出了一种基于轮询分组调度算法的节点选择与用户调度策略.与之前所提出的中继选择选择算法相比,所提出的中继节点轮询分组调度算法,不需要额外的信令开销,复杂度低,并保证中继间的负载均衡.此外,为保证用户传输的公平性,提出一种结合多用户分集的轮询分组调度算法.最后在已选择的中继节点和所调度的源节点用户中引入分布式空时编码.仿真结果表明,该节点选择和用户调度算法能保证所有节点使用的公平性,并且结合分布式空时编码之后,可以提高频谱利用率,从而提高了系统性能.     

A multiple-criteria real-time scheduling approach for multiple-load carriers subject to LIFO loading constraints

This paper studies the problem of scheduling a multiple-load carrier subject to last-in-first-out loading constraints in an automobile assembly line. Two scheduling criteria, the throughput of the assembly line and the material handling distance, are considered in order to maximise the profit of the assembly line. Different from other studies, the product mix and weights of the scheduling criteria are considered to be variable. A scheduling approach is proposed for the problem. At moments when the product mix or weights of the scheduling criteria change, the scheduling approach can select an appropriate rule from a set of given rules. In this study, the proposed approach is compared with other approaches by simulation in order to verify the performance of the proposed approach. The results indicate that, when the product mix and weights of the scheduling criteria are variable, the proposed scheduling approach outperforms other approaches.     

A general framework for scheduling equipment and manpower at container terminals

In this paper, we propose a general model for various scheduling problems that occur in container terminal logistics. The scheduling model consists of the assignment of jobs to resources and the temporal arrangement of the jobs subject to precedence constraints and sequence-dependent setup times. We demonstrate how the model can be applied to solve several different real-world problems from container terminals in the port of Hamburg (Germany). We consider scheduling problems for straddle carriers, automated guided vehicles (AGVs), stacking cranes, and workers who handle reefer containers. Subsequently, we discuss priority rule based heuristics as well as a genetic algorithm for the general model. Based on a tailored generator for experimental data, we examine the performance of the heuristics in a computational study. We obtain promising results that suggest that the genetic algorithm is well suited for application in practice.     

Impact of real-time traffic characteristics on freeway crash occurrence: Systematic review and meta-analysis

The development of methods for real-time crash prediction as a function of current or recent traffic and roadway conditions is gaining increasing attention in the literature. Numerous studies have modeled the relationships between traffic characteristics and crash occurrence, and significant progress has been made. Given the accumulated evidence on this topic and the lack of an articulate summary of research status, challenges, and opportunities, there is an urgent need to scientifically review these studies and to synthesize the existing state-of-the-art knowledge.     

A note on “The general lot sizing and scheduling problem”

Fleischmann and Meyr (1997) develop a model for the lot sizing problem with sequence dependent setup costs. In this note we show that this model is limited to the case where production state between two consecutive periods is conserved only if the available capacity of the preceding period exceeds the minimum batch quantity. We generalize the model by modification.This complete issue was revised and published online in November 2004. The previous version contained a false date. Correspondence to: Haldun Süral     

A real-time scheduling mechanism for a flexible manufacturing system: Using simulation and dispatching rules

This paper presents a real-time scheduling methodology which uses simulation and dispatching rules for flexible manufacturing systems. We develop a scheduling mechanism in which job dispatching rules vary dynamically based on information from discrete event simulation that is used for evaluating candidate dispatching rules. In this paper, we improve and extend a previous research on simulation-based real-time scheduling by suggesting a more systematic framework for the scheduling mechanism through refinement of functions of modules in the mechanism, and by presenting and analysing various scheduling strategies used to operate the mechanism. The strategies are formed by combining two factors that might influence the performance of the mechanism: type of simulation model which is used in the mechanism and points of time when new dispatching rules are selected. In order to compare performance of the scheduling strategies, computational experiments are performed and results are reported.     

基于任务同步及节能的单机系统实时动态调度算法

提出了一种基于任务同步及节能的单机系统实时混合动态调度算法(HDSA), 以有效解决能耗及实时任务同步时的优先权反转所导致的缺乏实时可调度性的问题.HDSA包含静态算法及动态算法两部分.静态算法可在静态条件下, 固定临界区的运行速度, 并求出非临界区部分的静态速度. 动态调度算法在实际运行中, 在满足周期性任务实时可调度性及任务同步的条件下, 充分利用及回收任务运行时剩余的执行时间, 调节处理器的速度, 以有效降低能耗.同时也能避免高优先权任务被阻塞时, 低优先权任务的临界区继承高优先权任务的速度所造成的处理器电压开关的频繁切换, 故能有效地降低实时任务调度的成本.实验测试表明HDSA在调度性能上明显优于相关的有效算法.     

Application of the generalised ballot theorem for evaluation of performance in packet buffers with non-first in first out scheduling

Packet scheduling is a vital component to support different classes of service in all-packet networks. In classical queuing systems, the waiting-time performance of non-first in first out buffer scheduling systems could be predicted through the use of analysis. However, all-packet networks feature traffic patterns that do not conform to classical Poisson-like processes, and this greatly complicates the evaluation of their performance. Our novel approach to this problem is through a hybrid combination of analysis and simulation. The authors derive a combinatorial algorithm, using the generalised ballot theorem, which predicts waiting times for low-priority traffic. When this algorithm is combined with prior work on traffic aggregation, the authors achieve a significant reduction in the state space associated with the buffer under study. To numerically test this algorithm, the authors demonstrate its use in simulation, where state space and event count reduction is a fundamental requirement to ensure experiments complete in a timely fashion. Numerical results from these simulations show a very significant reduction in the number of events processed combined with improved state coverage. This is achieved while maintaining a highly accurate representation of packet delays compared with a conventional approach.