Real-Time Systems Communication

DHT-Mesh: DHT-based services for increasing the scalability of highly available wireless mesh networks

Leader: Francisco Vasques de Carvalho
Period: From 2009/09/01 to 2012/12/30

See Details

A Wireless Mesh Network (WMN) is a dynamically self-organized and self-configured network. WMNs afford several potential advantages such as high network capacity, high connectivity and high resilience to failures and enable quick deployment. These features make them suitable for a wide range of applications. Typical examples include community and neighbourhood networking, enterprise networking, metropolitan area networks, transportation systems, building automation, healthcare and medical systems, and emergency/disaster networking support.

Despite the highly active research in wireless mesh networking, and the advances it achieved, many research challenges remain open to further inquiry. In order to contribute to the WMNs development, the goal of the DHT-Mesh project is to address the scalability problems of the IEEE 802.11s WMN draft standard.

The IEEE 802.11s (draft) standard is one of the most promising Wireless Local Area Network (WLAN) technologies. It relies on other widely deployed IEEE 802.11 standards for the physical layer and specifies a set of additional functions for medium access, and topology learning and routing. Although more scalable than the basic protocols for ad-hoc networking specified in earlier 802.11 standards, these algorithms still rely on broadcast, limiting the network to about 50 mesh points (MP) [1]. The DHT-Mesh project uses Distributed Hash Tables (DHTs) to make routing and topology learning less dependent on broadcast communication, and therefore more scalable. Unlike the DHTs used in peer-to-peer applications that operate at the application level, the DHTs used in the DHT-Mesh protocol operate at the medium access control (MAC) level. DHTs are distributed implementations of hash tables that allow for the efficient mapping of a key into a piece of information. Essentially, a DHT stores key-value pairs in different nodes, and provides a routing protocol among these nodes for looking up the keys that allows for the retrieval of the value in a number of hops in the order of log(n), where n is the number of DHT nodes.

More specifically, the main idea of the project is to limit the use of broadcast communication to learn the topology of only a small fraction of the MPs in a WMN. These nodes are then used to implement a DHT that is used when forwarding packets whose destinations are other nodes. Essentially, we replace the messages required to flood the mesh with routing information pertaining to some nodes, which is roughly proportional to the number of nodes, with a lookup in a DHT, which takes log(n) messages. The DHT-Mesh project proposes to explore this idea along two lines. First, to use it when forwarding packets to non-mesh nodes, such as wireless nodes attached to a mesh access point (MAP). These nodes will most likely outnumber the mesh nodes, i.e. the MPs, and will enter and leave the mesh much more frequently than the MPs. Thus by eliminating the need for broadcasting routing information for non-mesh nodes, DHTs allow for a sizable reduction in the routing traffic in a WMN.

Second, to use it together with "clustering". The idea is to group near-by mesh nodes in clusters. In each cluster, its MPs run an intra-cluster routing protocol. An inter-cluster routing protocol is run between only a few MPs of each cluster that are responsibe for forwarding frames between clusters. This allows to reduce the amount of routing information that needs to be exchanged between clusters. The missing information, required upon forwarding frames to other clusters, is retrieved from the DHT. Finally, the DHT-project proposes the use of DHTs both for IP address resolution, replacing the ARP protocol, and for mobility support.

To evaluate the effectiveness of DHT-based WMNs, both simulation and experimental evaluations are proposed. Furthermore, we propose to evaluate DHT-based WMNs in a real world application: a healthcare localization service to track both patients and medical staff in a hospital. This application has very stringent requirements making it rather appropriate to evaluate the proposed solutions: the number of nodes in the system is in the order of a few hundreds, many of these nodes are mobile and the application requires both high availability and real-time responsiveness.

Safe-DuST: Support for safety-critical applications in dual-scheduled TDMA-based networks

Leader: Francisco Vasques de Carvalho
Period: From 2008/02/01 to 2010/07/31

See Details

Dual-scheduled TDMA-based (DuST) medium access control protocols are a new class of medium access control protocols that was designed for safety-critical applications. In contrast with conventional TDMA-based protocols that support static scheduling only, DuST protocols support both static and dynamic scheduling. The automotive industry, in particular, has shown great interest in these protocols and many car manufacturers, and automotive electronics companies, have formed a consortium for the development of a protocol of this kind, FlexRay. It is expected [1, 2] that FlexRay will be adopted as the next generation communication system for automotive applications, replacing both less flexible TDMA-based protocols, such as TTP/C, with static scheduling only, and protocols with dynamic scheduling only, such as CAN. The latter make it hard to assure that the hard real-time requirements of the applications are met, whereas the former provide no support for non-periodic traffic and as consequence are less bandwidth efficient when applications have mixed traffic requirements. Because of the size of its potencial market, tens of million cars are manufactured every year, and the safety of persons is at stake, this new class of TDMA protocols is very important and deserves careful scrutiny.

Virtually all work on DuST protocols has focused on basic communication services required for safety-critical applications. In this project, we will focus on higher-level services. We propose to investigate new algorithms for group-membership and reliable broadcast that take advantage of the dual scheduling capability of protocols such as FlexRay. It is widely accepted [2, 3] that such core services facilitate the systematic development of safety-critical applications. The basic idea is to schedule the non-periodic traffic generated by these services in the part of the TDMA-cycle with dynamic scheduling. Therefore, in a "quiescent" state, when no aperiodic traffic is generated by these services, the bus bandwidth reserved for dynamic scheduling may be used by other aperiodic traffic. An example of this approach is illustrated by a group-membership protocol [4] that we have designed. Group membership protocols comprise two basic tasks: failure detection and set agreement, i.e. group membership agreement. In that protocol we rely on static scheduled messages to perform failure detection, and perform set agreement in the dynamic scheduled part of a cycle only when a failure is detected. In order to provide a higher assurance on the correctness of the proposed protocols, in addition to traditional "hand proofs", we will use formal methods, namely model checking. The correctness of core services that are intended to be used as building blocks of safety-critical applications is essential, as any flaw in such a service may lead to failure of the application. On the other hand, traditional "hand proofs" are very hard and even renowned researchers have published incorrect protocols with respective "proofs". By using model checking we intend to provide higher assurance on the correctness of our protocols. Finally, we will develop models to evaluate the reliability of the proposed protocols.

From a pratical point of view, the reliability of a service intended for safety-critical applications is very important. In proving a protocol correct we make assumptions regarding the types, number and rate of faults that system components may have. However, in a real system, these assumptions will hold only with a given probability that must be estimated. In summary, we propose to design group-membership and reliable broadcast protocols that take advantage of DuST protocols, prove them correct and assess their reliability. Thus the project is organized in six tasks. In the first Task we will develop and prove correct novel group membership protocols. In Tasks 2 and 3 we will use model checking to verify the correctness of those protocols, and will evaluate their performance and reliability, respectively. Tasks 4, 5 and 6 are analogous to Tasks 1, 2 and 3, respectively, but will focus on protocols for reliable broadcast.

[1] R. Makowitz, and C. Temple, "FlexRay - A Communication Network for Automotive Control Systems", in In Proceedings of the 2006 IEEE International Workshop on Factory Communication Systems (WFCS´06), 2006.
[2] N. Navet, Y. Song, F. Simonot-Lion, and C. Wilwert, "Trends in Automotive Communication Systems", Proc. of the IEEE, Vol 93, No. 6, June 2005.
[3] J. Rushby. A Comparison of Bus Architectures for Safety-Critical Embedded Systems. NASA CR-2003-212161. March 2003.
[4] V. Rosset, P. Souto, and F. Vasques. "A Group Membership Protocol for Communication Systems with both Static and Dynamic Scheduling." In Proceedings of the 2006 IEEE International Workshop on Factory Communication Systems (WFCS´06), 2006, pp. 23-32.

SiDETRAil: Real-time embedded systems for automation systems applications

Leader: Francisco Vasques de Carvalho
Period: From 2007/01/01 to 2008/12/31

No description available

VTP-CSMA: Real-time communication in 802.11 wireless networks

Leader: Francisco Vasques de Carvalho
Period: From 2004/01/01 to 2007/06/30

See Details

Nowadays, there is a trend for the use of wireless communications in industrial environments. This trend comes in the wake of an increasing use of wireless communications in the office and at home. However, communication requirements in industrial environments are very specific. In addition to generic traffic, e.g. data and multimedia traffic, similar to that found in the office/home environments, there is traffic that has hard real-time requirements.

This traffic is typically associated with control applications, where real-time (RT) control data must be periodically transferred between sensors, controllers and actuators according to strict transfer deadlines. Therefore one of the fundamental questions that must be addressed when setting up wireless industrial communication systems is: how to guarantee the timing requirements of RT control data, when the communication medium is shared with unconstrained multipurpose traffic?

The main objective of VTP-CSMA project is to provide an answer to this question. That is, we propose to develop appropriate mechanisms to support wireless RT communication services over an IEEE 802.11 wireless communication infrastructure, that is also being used to support generic multimedia and background data transfer applications. The goal is to address the hard real-time requirements of typical industrial wireless applications.

NCS-COM: Real-time communication mechanisms for control systems interconnected by industrial communication networks

Leader: Francisco Vasques de Carvalho
Period: From 2004/01/01 to 2005/12/31

See Details

The use of a communication network to interconnect controllers, sensors and actuators, in a Networked Control Systems (NCS), imposes specific real-time requirements upon the communication infrastructure. Basically, control applications require a predictable delay between measurement and actuation, with small variability, i.e., small jitter. Therefore, communication networks intended to support NCS must impose higher priority for the transfer of privileged (real-time) traffic. The main target of this project is to propose and assess innovative real-time communication mechanisms to support NCS.

copyright © UISPA, 2009

Danilo Fernandes
Joana Quintela