Betweenness estimation in OLSR-based multi-hop networks for distributed filtering

In traditional networks special efforts are put to secure the perimeter with firewalls: particular routers that analyze and filter the traffic to separate zones with different levels of trust. In wireless multi-hop networks the perimeter is a concept extremely hard to identify, thus, it is much more effective to enforce control on the nodes that will route more traffic. But traffic filtering and traffic analysis are costly activities for the limited resources of mesh nodes, so a trade-off must be reached limiting the number of nodes that enforce them. This work shows how, using the OLSR protocol, the centrality of groups of nodes with reference to traffic can be estimated with high accuracy independently of the network topology or size. We also show how this approach greatly limits the impact of an attack to the network using a number of firewalls that is only a fraction of the available nodes.     

Monitoring distributed real-time systems

This paper emphasizes the power ofmonitoring of distributed real-time systems as a promising tool for both scientific work and practical purposes. Starting out from a number of well-known problems with today's (industrial) real-time systems, a classification of remedial monitoring applications is given. The most important features of a monitoring system suitable for such purposes are discussed and related to the current research into monitoring of (general) distributed systems. Finally, some of the resulting conceptual issues underlying our prototype VTA monitoring system—currently being under development at our department—are presented.     

Modeling distributed real-time systems with MAST 2

Switched networks have an increasingly important role in real-time communications. The IEEE Ethernet standards have defined prioritized traffic (802.1p) and other QoS mechanisms (802.1q). The Avionics Full-Duplex Switched Ethernet (AFDX) standard defines a hard real-time network based on switched Ethernet. Clock synchronization is also an important service in some real-time distributed systems because it allows a global notion of time for event timing and timing requirements. In the process of defining the new MAST 2 model, clock synchronization modeling capabilities have been added, and the network elements have been enhanced to include switches and routers. This paper introduces the schedulability model that will enable an automatic schedulability analysis of a distributed application using switched networks and clock synchronization mechanisms.     

支持多媒体业务的新型无线多跳网络MAC协议*

提出了一种单信道无线多跳网络同步媒体接入控制协议—M-TDMA。基于信道预约,协议采用分类调度机制以满足多媒体业务中各类业务的服务质量需求。协议采用信道使用列表（CUL）、预约控制时隙、划分竞争期和非竞争期等措施维护预约信道,降低分组冲突率,提高信道使用率。分析结果表明,协议在保证分组传输可靠性的同时,传输时延较低,能够较好地支持多媒体业务的服务质量需求。     

多跳Ad Hoc网络视频实时传输性能评估

设计并开发了一种新的实时半实物Ad Hoc网络仿真平台,并基于此平台对压缩视频在多跳Ad Hoc网络中实时传输的性能进行了研究。比较了AODV、Bellmanford、DSR、Fisheye、ZRP等多种路由协议对实时视频业务的支持能力。结果表明,视频分组成功投递率（PDR）对视频流的解码回放质量起着至关重要的作用,在路由跳数大于某一门限值以后,PDR随着中继节点数量的增多呈近似线性下降,即使是PDR性能最好的Bellmanford路由协议,在多于5跳（PDR降至72%以下）的情况下也无法提供令人接受的视频质量。     

Optimal distributed real-time scheduling of flexible manufacturing networks modeled as hybrid dynamical systems

The paper considers a class of flexible manufacturing networks. We employ hybrid dynamical systems to model such networks. The main and new achievement of the paper is that we propose a distributed implementable in real time scheduling rule such that the corresponding closed-loop system is stable and optimal. In stable systems the processes converge to periodic ones. The paper gives computing relations for the determination of the parameters of the periodic processes. These are very much suitable for planning purposes. On this basis—and this, we consider, is also a new, significant result—optimal arrival (demand) rates determination method is proposed. Quality characteristics are outlined. Field of application of hybrid dynamical approach for FMS scheduling is analyzed. The results open perspectives for MRP level task planning. Example and simulation results are presented.     

Task scheduling in distributed real-time systems

An approach to the flow shop scheduling of the computation process in distributed realtime systems is considered. This approach is based on the concept of a solvable class of systems for which simple optimal scheduling algorithms exist.     

Language constructs for real-time distributed systems

The paper observes syntactic and semantic requirements for a language for programming real-time distributed systems. A proposal for language features that meet these requirements is offered, and the features are applied to an example.     

Synchronized UTC for distributed real-time systems

We present a novel technique for establishing a highly accurate global time in fault-tolerant, large-scale distributed real-time systems. Unlike the usual clock synchronization approaches, our clock validation technique provides a precise system time that also relates to an external time standard like UTC with high accuracy. The underlying idea is to validate time information of external time sources like GPS-receivers against a global time maintained by the local clocks in the system. As an example, a promising interval-based clock validation algorithm ICV that exhibits excellent fault-tolerance properties is outlined and analyzed. It requires only a few high-accurate external time sources and provides each node with the actual accuracy of its clock.     

实时性分布嵌入式系统设计

分布嵌入式系统的应用通常具有实时性要求,其实时性需要从任务调度、通信协议、调用接口和嵌入式操作系统四个方面得到支持。采用两阶段调度策略既可以保证调用的透明性,又可以简化任务调度算法;基于优先级的线路竞争算法可以改进以太网使其符合实时性要求;采用微型Java虚拟机作为分布式中间件可以为系统调用接口提供一个统一的支持平台。     

Virtual machines for distributed real-time systems

The steady increase in raw computing power of the processors commonly adopted for distributed real-time systems leads to the opportunity of hosting diverse classes of tasks on the same hardware, for example process control tasks, network protocol stacks and man–machine interfaces.This paper describes how virtualization techniques can be used to concurrently run multiple operating systems on the same physical machine, although they are kept fully separated from the security and execution timing points of view, and still have them exhibit acceptable real-time execution characteristics.With respect to competing approaches, the main advantages of this method are that it requires little or no modifications to the operating systems it hosts, along with a better modularity and clarity of design.     

Static analysis of real-time distributed systems

A static analysis for reasoning about the temporal behaviors of programs in real-time distributed programming languages is proposed. The analysis is based on the action set semantics using the pure maximal parallelism model. It is shown how to specify and verify various timing properties of real-time programs. The approach provides only an approximate timing behavior, because the state information is ignored. However, many interesting properties such as parallel actions, deadlocks, livelocks, terminations, temporal errors, and failures, can be identified. Furthermore, the approach is compositional and thus makes it possible to reason about the timing properties incrementally. The method not only leads to efficient algorithms for the static analysis of CSP programs but also applies to many other languages     

Efficient verification of distributed real-time systems with broadcasting behaviors

Binary synchronization has been used extensively in the construction of mathematical models for the verification of embedded systems. Although it allows for the modeling of complex cooperation among many processes in a natural environment, not many tools have been developed to support the modeling capability in this regard. In this article, we first give examples to argue that special algorithms are needed for the efficient verification of systems with complex synchronizations. We then define our models of distributed real-time systems with synchronized cooperation among many processes. We present algorithms for the construction of BDD-like diagrams for the characterization of complex synchronizations among many processes. We present weakest precondition algorithms that take advantage of the just-mentioned BDD-like diagrams for the efficient verification of complex real-time systems. Finally, we report experiments and argue that the techniques could be useful in practice.     

Computer networks and distributed systems

Three major justifications for distributed computing-sharing physically distributed resources, combining computers for fast solutions, and providing reliability through replication-are discussed. Distributed computing milestones from 1969 to 1991 are examined, focusing on the ARPAnet national research network, Ethernet and token-ring local area networks, and workstation networks united by distributed systems software. Three themes that dominate current trends in distributed systems and computer networks are examined. They comprise tapping the immense data-carrying potential of optical fibers, efficiently using tightly coupled networks of thousands of computers, and making network access inexpensive so many people will buy services. Developments for the next decade are predicted by extrapolating from these trends     

无人机多跳自组网实时视频传输性能评估

基于当前无人机广泛采用的M-JPEG与MPEG-2视频编解码器,构建了实时半实物仿真环境,并基于此对无人机多跳自组网实时视频传输进行了性能评估。结果表明,实时条件下的M-JPEG编解码器无法支持多跳实时视频传输,而MPEG-2能够支持2跳至3跳的实时视频传输;在1~10跳的实时传输条件下,MPEG-2较之M-JPEG在分组投送成功率和解码率意义下的视频质量平均分别提高了55.69%和205.64%。相对于传统的单飞单控方式,无人机多跳自组网在将无人机系统的作用范围扩大4~9倍的同时能够支持实时视频传输。     

Task response time for real-time distributed systems with resourcecontentions

An analytic model is proposed for estimating task response times in distributed systems with resource contentions. The model consists of two submodels. The first submodel is an extended queuing network model used for approximating module response times. This submodel is solved by a decomposition technique which reduces the computational complexity by two to three orders of magnitude when compared with a direct approach. The second submodel is a weighted control-flow graph model from which task response time can be obtained by aggregating module response time in accordance with the precedence relationships. Task response times estimated by the analytic model compare closely with simulation results. It is shown that resource contention delays depend on the availability of resources as well as on the invocation rates and response times of the modules that use the resources. The model can be used to study the tradeoffs among module assignments, scheduling policies, interprocessor communications, and resource contentions in distributed processing systems     

Supporting lock-free synchronization in Pfair-scheduled real-time systems

We consider the use of lock-free techniques for implementing shared objects in real-time Pfair-scheduled multiprocessor systems. Lock-free objects are more economical than locking techniques when implementing relatively simple objects such as buffers, stacks, queues, and lists. However, the use of such objects on real-time multiprocessors is generally considered impractical due to the need for analytical real-time guarantees. In this paper, we explain how the quantum-based nature of Pfair scheduling enables the effective use of such objects on real-time multiprocessors and present analysis specific to Pfair-scheduled systems. In addition, we show that analytical improvements can be obtained by using such objects in conjunction with group-based scheduling techniques. In this approach, a group of tasks is scheduled as a single entity (called a supertask in the Pfair literature). Such grouping prevents tasks from executing simultaneously, and hence from executing in parallel. Consequently, grouping tasks can improve the worst-case scenario with respect to object contention. Grouping also enables the use of less costly uniprocessor algorithms when all tasks sharing an object reside within the same group. We illustrate these optimizations with a case study that focuses on shared queues. Finally, we present and experimentally evaluate a simple heuristic for grouping tasks in order to reduce object contention. Though the analysis presented herein focuses specifically on Pfair-scheduled systems, the observations and techniques should be applicable to other quantum-scheduled systems as well.     

Fundamental issues in testing distributed real-time systems

This paper examines the fundamental problems that one faces when testing a distributed, hard real-time system. It specifically identifies the influences of the distributedness and of the real-time requirements of the systems considered. We show how the usual problems of testing become more difficult, and which additional problems are introduced, because of these additional system characteristics.We identify six such fundamental problems: Organization, Observability, Reproducibility, Host/Target Approach, Environment Simulation, and Representativity. These, as well as their interrelations, are presented in a general framework that is independent of a particular system architecture or application. This framework could serve as a starting point for all activities geared towards a particular system architecture or a specific application.As an example, we illustrate how these test problems have been handled when developing a test methodology for the distributed real-time system MARS. Finally, the additional issues of test data generation and test result analysis are briefly discussed.     

Performance estimation for real-time distributed embedded systems

Many embedded computing systems are distributed systems: communicating processes executing on several CPUs/ASICs. This paper describes a performance analysis algorithm for a set of tasks executing on a heterogeneous distributed system. Tight bounds are essential to the synthesis and verification of application-specific distributed systems, such as embedded computing systems. Our bounding algorithms are valid for a general problem model: The system can contain several tasks with hard real-time deadlines and different periods; each task is partitioned into a set of processes related by data dependencies. The periods of tasks and the computation times of processes are not necessarily constant and can be specified by a lower bound and an upper bound. Such a model requires a more sophisticated algorithm, but leads to more accurate results than previous work. Our algorithm both provides tighter bounds and is faster than previous methods     

Modular abstractions for verifying real-time distributed systems

In this work we present a verification methodology for real-time distributed systems, based on their modular decomposition into processes. Given a distributed system, each of its components is reduced by abstracting away from details that are irrelevant for the required specification. The abstract components are then composed to form an abstract system to which a model checking procedure is applied. The abstraction relation and the specification language guarantee that if the abstract system satisfies a specification, then the original system satisfies it as well.The specification languageRTL is a branching-time version of the real-time temporal logicTPTL presented in Alur and Henzinger [1]. Its model checking is linear in the size of the system and exponential in the size of the formula. Two notions of abstraction for real-time systems are introduced, each preserving a sublanguage ofRTL.