Optimal scheduling with deadline constraints in tree networks

The problem of scheduling time-critical messages over a tree network is considered. Messages arrive at any of the nodes and have to reach the root node before their deadlines expire, else they are considered lost. The network is assumed to be operating in discrete time and the messages need one time unit for transmission from one node to the next along its path. The arrival and deadline processes are arbitrary. The policy which transmits messages with smallest extinction (arrival+deadline) time at every link is shown to minimize the number of lost messages over all time intervals and for every sample path     

Routing Messages with Release Time and Deadline Constraint

The problem of determining whether a set of real-time messages can be routed in a network is considered. Each message has five parameters-origin node, destination node, length, release time, and deadline. The complexity of the problem is considered under various restrictions of four parameters-origin node, destination node, release time, and deadline. It is shown that if the network is a arbitrary directed graph, the problem is NP-complete even when all four parameters are fixed; i.e., the messages have identical values in all four parameters. Motivated by the complexity of the problem, we consider a simple network-a unidirectional ring. For nonpreemptive transmission, it is shown that the problem is solvable in polynomial time if three of the four parameters are fixed, but becomes NP-complete if only two of them are fixed. The same kind of complexity results hold for preemptive transmission, except for the following two cases: (1) identical origin nodes and release times and (2) identical destination nodes and deadlines. The complexity of these two cases remains open. The issue of whether there is an optimal on-line algorithm is also considered. It is shown that no such algorithm can exist unless all of the remaining three parameters are fixed.     

Network access protocol for hard real-time communication systems

Distributed hard real-time systems are characterized by communication messages associated with timing constraints, typically in the form of deadlines. A message should be received at the destination before its deadline expires. Carrier sense multiple access with collision detection (CSMA/CD) appears to be one of the most common communication network access schemes that can be used in distributed hard real-time systems. In this paper, we propose a new real-time network access protocol which is based on the CSMA/CD scheme. The protocol classifies the messages into two classes as ‘critical’ and ‘noncritical’ messages. The messages close to their deadlines are considered to be critical. A critical message is given the right to access the network by preempting a noncritical message in transmission. Extensive simulation experiments have been conducted to evaluate the performance of the protocol. It is shown that the protocol can provide considerable improvement over the virtual time CSMA/CD protocol proposed for hard real-time communication by Zhao et al.¹.     

主从交换式以太网中跨多Switch传输消息实时调度研究

针对FTT-SE协议在单Master多交换机的网络扩展结构中存在的消息跨多Switch传输调度问题,给出了消息在每个基本调度周期内到达各交换机输出端口时间的计算方法,提出了单EC内的消息可调度性判定算法,并对算法的可行性进行了证明。在此基础上,设计了基于EDF的消息实时调度算法和准入控制算法。通过确定消息在每个基本调度周期内到达各交换机输出端口时间,所提出的调度算法能针对COTS交换机输出端口的FCFS消息传输机制,实现对单EC内消息传输的精确控制和调度。相对已有的调度算法,仿真实验表明,所提出的算法能更有效地利用网络带宽,提高了主从交换式以太网通信的实时性。     

DTN中基于生命游戏的拥塞控制策略

为了应对容迟网络中拓扑结构剧烈变化、节点间连接频繁中断等问题,报文通常采用“存储—携带—转发”的方式进行传输：节点将报文存储在缓存中,携带报文直到遇到合适的机会才将报文转发给其他节点.因为缓存有限,这样的传输方式会使节点缓存溢出,导致拥塞的发生.在容迟网络环境下提出一种基于生命游戏的拥塞控制策略(game of life based congestion control strategy in delay tolerant networks, GLCCS),并将其应用于Epidemic路由方式.GLCCS借鉴生命游戏的演化思想,依据邻居节点中持有特定报文的节点比例来决定节点本地缓存中相应报文的操作.同时还提出了基于全网信息的报文排队机制和丢弃策略,依据传递或者丢弃一个报文对整个网络投递成功率的影响,计算出报文的效用值,按照效用值对缓存中报文进行排队和丢弃.在机会网络模拟器ONE中对仿真移动模型和真实运动轨迹进行模拟,实验结果表明,GLCCS与其他拥塞控制策略相比提高了投递成功率,减小了网络时延、丢包率以及负载比率.     

基于LoRaWAN的自适应多帧高效传输方法

针对LoRaWAN协议中LoRa网关与LoRa终端间数据多帧传输方式存在控制开销和传输时延较大的问题,提出一种基于LoRaWAN的自适应多帧高效传输方法（adaptive multi-frame efficient transmission,AMFET）,包含自适应多帧发送机制、自适应多帧接收确认机制和丢帧识别机制。自适应多帧发送机制对需确认数据消息设置优先等级,对高级需确认数据消息进行立即确认,对低级需确认数据消息在自适应发送模式结束后统一进行确认,同时将Fpending机制引入LoRaWAN上行多帧传输;自适应多帧接收确认机制通过位向量压缩技术记录已接收数据帧信息,从而单次对多个需确认数据消息进行合并确认;丢帧识别机制利用需确认帧编号（confirmed data identity,CDID）识别低级需确认消息是否丢失,避免终端异常进入休眠模式。通过数学分析和实验测试,分别对AMFET方法的性能进行了理论验证和实验验证,验证结果表明,相对于原LoRaWAN多帧传输方式,AMFET方法在保证数据传输可靠性的前提下,有效降低了数据传输时延和数据传输能耗。     

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.     

Testing the Schedulability of Synchronous Traffic for the Timed Token Medium Access Control Protocol

One of the key issues related to guaranteeing synchronous message deadlines in a timed token network (such as fiber distributed data interface) where the timed token medium access control protocol is used is the schedulability test of synchronous traffic (i.e., testing whether or not all synchronous messages can be transmitted before their deadlines, under a given setting of network parameters). Much work has been done on how to assign network parameters appropriately in order to guarantee timely transmission of synchronous traffic. As a result quite a few synchronous bandwidth allocation schemes and some good guidelines on selection of the target token rotation time have been proposed. In contrast, limited research has been conducted on how to effectively test whether or not given network parameters can guarantee timely transmission of all synchronous messages (of a considered synchronous message set) before their deadlines. The previous testing methods for synchronous message schedulability only provide a sufficient (but not necessary) test and therefore fail to always keep effective for any synchronous message set considered. In this paper, we propose two testing methods for determining the schedulability of a synchronous message set with message deadlines no longer than periods. The proposed tests perform better than any previous test in the sense that they are both sufficient and necessary. Some numerical examples are given to compare different testing methods, all of which have demonstrated the superiority of the proposed tests to other existing testing methods.     

PC机群上JIAJIA与MPI的比较

对JIAJIA和MPI (message passing interface)是进行了比较.JIAJIA和MPI分别代表共享存储和消息传递的编程模式.MPI显式进行数据传输,编程复杂;JIAJIA由底层维护数据一致性,并附加提供简单的消息传递函数,编程容易、灵活.JIAJIA分配共享内存时开销较大,初始化时间比MPI长.提出了一个关于并行加速比与进程数目之间关系的近似经验公式,推出JIAJIA和MPI性能差距随着进程数目的增多而增大的结论.测试结果表明,大部分应用程序的JIAJIA和MPI版本的并行性能差距不超过10%.对于通信量很小的应用程序,其JIAJIA和MPI的性能差距较小,而通信量本身较大的应用程序,其JIAJIA和MPI的性能差距主要取决于运行时产生的实际通信量.     

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

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

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.     

The flooding sink — a new approach to local area networking

A new local area networking technology is presented. The approach is based on an old routing algorithm called flooding — forward messages to all neighbouring nodes. The problem with this algorithm is that the network is deluged with duplicate messaes. The solution is a simple device which uses local memory to detect and ignore redundant messages, thus also acting as a message sink. Networks based on this device can be more flexible and reliable than current networks. Flooding also has the advantage that any messages lost due to transmission errors are quickly replaced by one of the copies. This can make low-level protocols unnecessary. When the low-level protocols are omitted, significant performance improvements are achieved. Simulation results are presented which show that this flooding technology can perform better than current CSMA and ring technologies.     

Network Performance Under Bimodal Traffic Loads

In actual multicomputer networks, communications consist of hybrid traffic in which messages exhibit a variety of sizes. However, to date, most studies on network performance are based on traffic loads of uniformly-sized messages. We investigate the performance of wormhole-routed networks under bimodal traffic distributions, a mix of short and long messages. Our studies show that the presence of long messages degrades network performance for short messages dramatically, qualitatively changing network behavior. We present an analytical model for wormhole-routed networks which not only models network performance under uniformly sized message loads more accurately than existing models, but also can be extended to support bimodal traffic distributions. The model is validated against detailed simulation of routing networks, over a variety of message size distributions and message lengths. In virtually all cases, the model accurately predicts both network throughput and average message latency to within 8%. Because the impact of long messages can be severe, we consider three techniques-packetization, virtual lanes, and adaptive routing-to alleviate their impact. Packetization reduces the blocking time of long messages, improving network performance in most cases. Virtual lanes and adaptive routing together provide sufficient routing freedom to eliminate much of the blocking, producing performance comparable or even superior to that produced by packetization. Together, all three techniques are complementary, providing robust performance over a variety of traffic mixes and message sizes.     

Schemes for scheduling control messages by hierarchical protocols

The paper addresses the problem of designing efficient scheduling policies for the transmission of control messages by hierarchical network protocols. Such protocols encounter a tradeoff between the desire to forward a control message across the tree as soon as it is received, and the desire to reduce control traffic. Scheduling problems that arise in this context are defined and discussed. The paper mainly concentrates on minimizing the average extra delay encountered by the control messages under an upper bound on the number of outgoing messages a node can send during a fixed period of time. A polynomial-time algorithm is presented for the off-line version of the problem, and then several efficient on-line heuristics are presented and compared.     

Dealing with inconsistent secure messages by weighting majority

Messages transmitted between senders and receivers might be inconsistent owing to potential communication block, message lost and/or malicious attacks, in electronic commerce. And current formal methods for security protocol analysis show limitations in handling the incoherent secure messages that may be derived from different sources or at different moments. This results in increasing risk of e-commerce activities. This paper thus proposes a formal framework to deal with the inconsistency in secure messages by weighting majority. The freshness and dynamics properties of secure messages are considered and a reliability function is developed to measure the belief in secure messages. This helps us verify protocols in an intuitive way and guarantees correct verification results. The experimental results demonstrate our method is useful in secure protocol analysis.     

一种基于网络编码的新型卫星网络可靠组播机制

卫星信道的天然广播及广域覆盖等特性使得基于卫星网络开展组播服务具有很强的吸引力,然而,卫星链路长时延、高误码、非对称的特点容易导致报文大量丢失和重传,使得组播可靠性难于保证。提出了一种基于网络编码的卫星网络可靠组播机制(NCM)。NCM通过在发送端主动发送原始报文的冗余编码包,可实现接收端多个丢失报文的本地恢复;同时结合传统ARQ反馈重传,当出现原始报文和编码包同时丢失时,通过重传编码包,就可恢复多个丢失报文。理论分析和仿真实验表明了该机制的可行性和有效性。     

基于发布/订阅模型的异构网络数据交换方法

消息数据高效传输是混合式网络的一个研究重点. 发布/订阅模型实现了消息发布者和消息订阅者之间解耦的消息传递模式, 适用于混合网络之间的消息数据传输. 通过将发布/订阅模型应用于消息数据交换, 规范了消息数据的格式, 实现了对各类通信设备的灵活管理以及基于消息内容的动态数据路由; 并利用一种基于循环调度的动态负载均衡算法, 对低速率网络和高速率网络之间的性能进行合理调度, 提高了低速率网络的性能. 模拟实验结果表明, 在混合式网络中发布/订阅模型能实现可靠的消息数据交换, 在负载平衡算法下性能更好.     

FC仲裁环实现实时传输的带宽分配方法

考虑实时消息的优先级顺序,对光纤通道仲裁环结构下研究实时性问题的“最差情形”做了补充和完善。重新定义保证数据传输实时性的2个限制条件,提出最差情形公平负载率的概念,从而将上述2个限制条件归结为一条,即要保证所有消息的实时性,必须使每个消息的最差情形公平负载率小于等于1,揭示数据传输的实时性与网络负载率之间的本质联系。考虑对实时消息进行拆分后增加的协议开销和物理层延时等影响因素,基于网络总负载率最小化原则给出一种简洁的带宽分配方法。通过实例仿真研究了仲裁环下假想消息集中的各个实时消息在“最差情形”下的带宽分配情况,证明该算法的正确性。     

An Optimal Algorithm for Broadcasting Multiple Messages in Trees

We consider multiple message broadcasting in tree networks. The source (considered as the root of the tree) has k messages which have to be broadcast to all nodes of the tree. In every time unit each node can send one of its already obtained messages to one of its children. A k-message broadcasting scheme prescribes in which time unit a given node should send a message to which child. It is k-optimal if it achieves the smallest possible time for broadcasting k messages from the source to all nodes. We give an algorithm to construct a k-optimal broadcasting scheme for an arbitrary n-node tree. The time complexity of our algorithm is O(nk), i.e., the best possible.     

Efficient rollback-recovery technique in distributed computingsystems

We propose an approach for implementing rollback recovery in a distributed computing system. A concept of logical ring is introduced for the maintenance of information required for consistent recovery from a system crash. Message processing order of a process is kept by all other processes on its logical ring. Transmission of data messages are accompanied by the circulation of the associated order messages on the ring. The sizes of the order messages are small. In addition, redundant transmission of order information is avoided, thereby reducing the communication overhead incurred during failure free operation. Furthermore, updating of the order information and garbage collection task are simplified in the proposed mechanism. Our approach does not require information about message processing order be written to stable storage; in fact, the time consuming operations of saving information in stable storage are confined to the checkpointing activities. When failures occur, a surviving process need roll back only if some preceding order information is totally lost, which is relatively unlikely considering the ever growing speed of communication networks. It is shown that a system can recover correctly as long as there exists at least one surviving process