A hybrid TDMA/Random-access scheme for multiple-access communication networks

A hybrid TDMA/Random-Access multiple-access (HTRAMA) scheme is introduced for providing an access-control coordination for a multi-access communication channel. Such a scheme is applicable to a large spectrum of computer communication network applications. Under this hybrid scheme, the system sources are divided into groups. Sources in different groups are allocated disjoint time slots for their transmissions. Sources within a group share their allocated time slots by transmitting according to a tree random-access policy. The number of groups (and their sizes) is dynamically adjusted to properly (and optimally) match the underlying channel traffic characteristics. In this fashion the hybrid scheme dynamically adapts to a random-access structure at lower traffic throughput levels and to a TDMA structure at higher throughput levels. We carry out detailed delay throughput analysis for these hybrid schemes under both limited and unlimited source buffer capacities. The hybrid scheme is demonstrated to yield very good delay-throughput performance curves under wide ranges of network traffic statistical fluctuations and spans.     

Fault-tolerant, real-time communication in FDDI-based networks

The first high-speed network to meet the Safenet standard's bandwidth requirements, the Fiber Distributed Data Interface (FDDI) needs help to meet Safenet's fault tolerance requirement. Researchers have proposed a number of FDDI-based network architecture designs for improving fault tolerance. An architecture called FBRN (FDDI-Based Reconfigurable Network) provides enhanced fault tolerance by using (a) multiple FDDI networks to connect hosts, and (b) efficient fault detection and network configuration algorithms. To provide fault-tolerant real-time communication with the FBRN architecture, users must manage network resources properly. We sought to accomplish this by using a fault-tolerant, real-time management mechanism with online and offline components. We focused on achieving high performance by designing efficient and effective online and offline management algorithms to work around multiple faults     

无人机强实时性串行通讯程序设计

研究了无人机飞行控制器通讯软件的实时性问题。运用中断服务程序就地帧识别、有限状态机、缓存共用和代码优化技术,设计了具有多通讯协议的强实时性串行通讯接收程序。经过实际运行测试,程序解码率高、可靠性好、实时性强、运行时间合理,满足了无人机飞行控制对串行通讯程序的性能要求。     

Guaranteed real-time communication in packet-switched networks with FCFS queuing

In this paper, we propose a feasibility analysis of periodic hard real-time traffic in packet-switched networks using first come first served (FCFS) queuing but no traffic shapers. Our work constitutes a framework that can be adopted for real-time analysis of switched low-cost networks like Ethernet without modification of the standard network components. Our analysis is based on a flexible network and traffic model, e.g., variable-sized frames, arbitrary deadlines and multiple switches. The correctness of our real-time analysis and the tightness of it for network components in single-switch networks are given by theoretical proofs. The performance of the end-to-end real-time analysis is evaluated by simulations. Moreover, our conceptual and experimental comparison studies between our analysis and the commonly used Network Calculus (NC) shows that our analysis can achieve better performance than NC in many cases.     

Experimental evaluation of behavior-based failure-detection schemesin real-time communication networks

Effective detection of failures is essential for reliable communication services. Traditionally, non-real-time computer networks have relied on behavior-based techniques for detecting communication failures. That is, each node uses heartbeats to detect the failure of its neighbors and the end-to-end transport protocol (e.g., TCP) achieves reliable communication by acknowledgment/retransmission. Recently, there has been a growing demand for reliable “real-time” communication, but little research has been done on the failure detection problem. In this paper, we present two behavior-based failure-detection schemes-neighbor detection and end-to-end detection-for reliable real-time communication services and experimentally evaluate their effectiveness. Specifically, we measure and analyze the coverage and latency of these detection schemes through fault-injection experiments. The experimental results have shown that nearly all failures can be detected very quickly by the neighbor detection scheme, while the end-to-end detection scheme uncovers the remaining failures with larger detection latencies     

Asymptotic analysis of queues in multiple-access computer networks

The paper considers local-area computer networks with a protocol that supports carrier-sense multiple access with instantaneous conflict detection and is a generalization of slotted ALOHA. An approach based on recurrent processes is applied to analyze the asymptotic behavior of the number of waiting calls under conditions of low retrial rate.Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 54–61, July–August, 1991.     

Collision-control algorithms in carrier-sense multiple-access (collision-detection) networks

The effects of the collision-control algorithm on CSMA-CD protocols are studied. After a comparative evaluation of some algorithms and an ideal scheduling system, the required features for an optimum collision-control algorithm are enumerated. Finally, a new algorithm, incorporating most of these features, is proposed, and its performance is evaluated.     

Multi-hop cellular networks: Architecture and protocols for best-effort and real-time communication

Until recently, research on cellular networks concentrated only in single-hop cellular networks. The demand for high throughput has driven to architectures that use multiple hops in the presence of infrastructure. We propose an architecture for multihop cellular networks (MCNs). MCNs combine the benefits of having a fixed infrastructure of base stations and the flexibility of Ad hoc networks. They are capable of achieving much higher throughput than current cellular systems, which can be classified as single-hop cellular networks (SCNs). In this work, we propose an extended architecture for MCN using the IEEE 802.11 standard for wireless LANs for connection-less service and a TDMA-based solution for real-time support. We provide a general overview of the architecture and the issues involved in the design of MCNs, in particular the challenges to be met in the design of a routing protocol, a channel assignment scheme, and a mobility management scheme. We also propose a routing protocol called Base-Assisted Ad hoc Routing (BAAR) protocol for use in such networks and a model for the performance analysis of MCNs and SCNs. We also conduct extensive experimental studies on the performance of MCNs and SCNs under various load (TCP, UDP, and real-time sessions) and mobility conditions. These studies clearly indicate that MCNs with the proposed architecture and routing protocol are viable alternatives for SCNs, in fact they provide much higher throughput. MCNs are very attractive for best-effort packet radio where they can achieve an increase in throughput up to four when compared to similar SCNs. But for real-time traffic, even though they do outperform SCNs, they also suffer from a few disadvantages such as frequent hand-offs and throughput degradation at high mobility. We also present results from a detailed comparison study of our architecture for MCN with the Hybrid Wireless Network (HWN) architecture and Integrated Cellular Ad hoc Relaying (iCAR) Architecture.     

Robust design of a linear quadratic power control algorithm in multiple-access networks

In wireless networks under interference, power control is of the utmost importance to guarantee Quality of Service during data transmissions. A distributed perspective is commonly preferred to design controllers in each mobile user in the network for power allocation. The round-trip delay is a characteristic feature of wireless networks, and it was considered a known quantity in previous works. In this paper, we do not follow this assumption and propose the design of the power controller only with the information of upper and lower bounds on the round-trip delay as functions of a frequency gain. In a second stage, we relate the proposed robust design to common performance indicators, such as the step response overshoot. The proposed design rules can be applied to design a suitable robust controller for power control in a wireless network subject to interference.     

Performance analysis of a cooperative symmetric algorithm for real-time local area computer communication networks

A hybrid algorithm for soft real-time local area networks is analyzed under conditions of no buffering and full buffering capability at nodes, and for synchronous and asynchronous networks. This algorithms is a variation of the Reservation Upon Collision (RUC) technique that does not require a synchronized slotted network, and operates on a broadband broadcast medium. It has the desirable first-in-first-out behavior, avoiding large variance in packet transmission times. Approximations to the upper and lower bounds on the capacity of the channel and the mean waiting time at the nodes are found. The performance figures of this algorithm attest to its suitability for soft real-time environments.     

Fault-tolerant real-time communication in distributed computingsystems

The delivery delay in a point-to-point packet switching network is difficult to control due to the contention among randomly-arriving packets at each node and multihops a packet must travel between its source and destination. Despite this difficulty, there are an increasing number of applications that require packets to be delivered reliably within prespecified delay bounds. This paper shows how this can be achieved by using real-time channels which make “soft” reservation of network resources to ensure the timely delivery of real-time packets. We first present theoretical results and detailed procedures for the establishment of real-time channels and then show how the basic real-time channels can be enhanced to be fault-tolerant using the multiple disjoint paths between a pair of communicating nodes. The contribution of the former is a tighter schedulability condition which makes more efficient use of network resources than any other existing approaches, and that of the latter is a significant improvement in fault tolerance over the basic real-time channel, which is inherently susceptible to component failures     

Statistical real-time communication over Ethernet

In order to realize real-time communication over Ethernet or fast Ethernet, one must be able to bound the medium access time within an acceptable limit. The multiple access nature of Ethernet makes it impossible to guarantee a deterministic medium access time (hence, packet-delivery deadlines) to individual stations. However, one can bound the medium access time statistically by limiting the packet-arrival rate at the medium access control (MAC) layer. While considering automated manufacturing systems as the main target application, this paper addresses the connection admission control (CAC) problem for statistically bounding the medium access time of Ethernet. Specifically, a packet is guaranteed to have a medium access time smaller than a predefined bound with a certain probability if the instantaneous packet-arrival rate is kept below a certain threshold. Through a mathematical analysis, we first derived such a threshold. In order to keep the packet-arrival rate under the given threshold, we developed and installed middleware which 1) resides between the transport layer and the Ethernet datalink layer, and 2) smooths packet streams between them. The implementation of this middleware requires only a minimal change in the OS kernel without modification to the current standard of Ethernet MAC protocol or TCP or UDP/IP stack. In order to solve the CAC problem, we derived the probability of transmitting a packet successfully upon each trial by modeling the MAC protocol, 1-persistent CSMA/CD, and the collision resolution protocol inary exponential backoff - of Ethernet. Our in-depth simulation results have shown this analytic model to provide a reasonably accurate estimate of packet-loss (or deadline-miss) ratio over fast Ethernet. Finally, we implemented the middleware on the Linux OS, experimentally demonstrating the effectiveness of our approach in providing real-time communication over Ethernet.     

Optimal polling in communication networks

Polling is the process in which an issuing node of a communication network (polling station) broadcasts a query to every other node in the network and waits to receive a unique response from each of them. Polling can be thought of as a combination of broadcasting and gathering and finds wide applications in the control of distributed systems. In this paper, we consider the problem of polling in minimum time. We give a general lower bound on the minimum number of time units to accomplish polling in any network and we present optimal polling algorithms for several classes of graphs, including hypercubes and recursively decomposable Cayley graphs     

Real-time communication in multihop networks

Communication in real-time systems has to be predictable, because unpredictable delays in the delivery of messages can adversely affect the execution of tasks dependent on these messages. We develop a scheme for providing predictable interprocess communication in real-time systems with (partially connected) point-to-point interconnection networks, which provide guarantees on the maximum delivery time for messages. This scheme is based on the concept of a real-time channel, a unidirectional connection between source and destination. A real-time channel has parameters that describe the performance requirements of the source-destination communication, e.g., from a sensor station to a control site. Once such a channel is established, the communications subsystem guarantees that these performance requirements will be met. We concentrate on methods to compute guarantees for the delivery time of messages belonging to real-time channels. We also address problems associated with allocating buffers for these messages and develop a scheme that preserves delivery time guarantees     

Multicast communication in multicomputer networks

Efficient routing of messages is a key to the performance of multicomputers. Multicast communication refers to the delivery of the same message from a source node to an arbitrary number of destination nodes. While multicast communication is highly demanded in many applications, most of the existing multicomputers do not directly support this service; rather it is indirectly supported by multiple one-to-one or broadcast communications, which result in more network traffic and a waste of system resources. The authors study routing evaluation criteria for multicast communication under different switching technologies. Multicast communication in multicomputers is formulated as a graph theoretical problem. Depending on the evaluation criteria and switching technologies, they study three optimal multicast communication problems, which are equivalent to the finding of the following three subgraphs: optimal multicast path, optimal multicast cycle, and minimal Steiner tree, where the interconnection of a multicomputer defines a host graph. They show that all these optimization problems are NP-complete for the popular 2D-mesh and hypercube host graphs. Heuristic multicast algorithms for these routing problems are proposed     

Real-time communication in FDDI networks

This paper provides a comprehensive study of the use of FDDI networks to support real-time communication in mission-critical systems. Due to the potentially catastrophic results of failure in such systems, it is important to avoid message loss whenever possible. We develop efficient tests to check whether message loss may occur, either due to missing deadlines or due to buffer overflow. These tests are extremely useful in the design and operation of mission-critical systems using FDDI networks. Two types of tests are developed: message-parameter-based tests, which use detailed system knowledge to determine whether loss may occur, and utilization-based tests, which only require knowledge of the overall system load. In order to examine the system performance over a wide range of network loads, we also examine the probability that a randomly chosen message set will not suffer any loss. The work reported in this paper is compatible with the FDDI and SAFENET standards, and can be applied by engineers building real-time systems using these standards.     

Hard real-time multibody simulations using ARM-based embedded systems

The real-time simulation of multibody models on embedded systems is of particular interest for controllers and observers such as model predictive controllers and state observers, which rely on a dynamic model of the process and are customarily executed in electronic control units. This work first identifies the software techniques and tools required to easily write efficient code for multibody models to be simulated on ARM-based embedded systems. Automatic Programming and Source Code Translation are the two techniques that were chosen to generate source code for multibody models in different programming languages. Automatic Programming is used to generate procedural code in an intermediate representation from an object-oriented library and Source Code Translation is used to translate the intermediate representation automatically to an interpreted language or to a compiled language for efficiency purposes. An implementation of these techniques is proposed. It is based on a Python template engine and AST tree walkers for Source Code Generation and on a model-driven translator for the Source Code Translation. The code is translated from a metalanguage to any of the following four programming languages: Python-Numpy, Matlab, C++-Armadillo, C++-Eigen. Two examples of multibody models were simulated: a four-bar linkage with multiple loops and a 3D vehicle steering system. The code for these examples has been generated and executed on two ARM-based single-board computers. Using compiled languages, both models could be simulated faster than real-time despite the low resources and performance of these embedded systems. Finally, the real-time performance of both models was evaluated when executed in hard real-time on Xenomai for both embedded systems. This work shows through measurements that Automatic Programming and Source Code Translation are valuable techniques to develop real-time multibody models to be used in embedded observers and controllers.     

Universal Timestamp-Scheduling for real-time networks

Consider a network of computers interconnected by point-to-point communication channels. For each flow of packets through the network, the network reserves a fraction of the packet rate of each channel along the path of the flow. We define a family of scheduling protocols, called Universal Timestamp-Scheduling, to forward packets in this network, such that all members of the protocol family provide the same upper bound on packet delay as the well-known packet delay of Virtual Clock scheduling. The protocol family is called universal because it encompasses a wide variety of protocols. To show this, we prove that many scheduling protocols in the literature are members of the protocol family, and thus provide the above guarantee. In addition, we show that the protocols in the literature have only considered one side of the spectrum of possible scheduling protocols, and that there is another side of the spectrum that deserves attention and remains to be investigated.     

Message scheduling for real-time interprocessor communication

In this paper an efficient algorithm is proposed which optimizes periodic message scheduling in a real-time multiprocessor system. The system is based on a many-core single-chip computer architecture and uses a multistage baseline network for inter-core communication. Due to its basic architecture, internal blockings can occur during data transfers, i.e. the baseline network is not real-time capable by itself. Therefore, we propose a scheduling algorithm that may be performed before the execution of an application in order to compute a non-blocking schedule of periodic message transfers. Additionally, we optimize the clock rate of the network subject to the constraint that all data transfers can be performed in a non-blocking way. Our solution algorithm is based on a generalized graph coloring model and a randomized greedy approach. The algorithm was tested on some realistic communication scenarios as they appear in modern electronic car units. Computational results show the effectiveness of the proposed algorithm.     

网络实时通讯的一种解决方案

本文介绍了利用以太网进行通讯的一种解决方案。该方案充分利用了嵌入式实时操作系统强实时性和稳定性及Windows操作系统强大的功能，提供了利用两种互补和协同工作的操作系统完成实时网络通讯新的思路。