IRIT - UMR 5505

Partenaires

Rechercher

Accueil du site > English > Research Topics > Topic 6 - Architecture, Systems and Networks > ASTRE team > Researches > Quality of Service in Networks and Embedded Systems

Quality of Service in Networks and Embedded Systems

Since more than two decades there is an increasing interest in real-time, embedded and distributed systems that handle critical or multimedia flows. These systems are used in many domains (health care, entertainment, avionics, telecommunications, transportation…). They have strong constraints in terms of security, fault tolerance, and quality of service (QoS). Constraints to consider are so much numerous, making the design and validation of such systems hard tasks. It also is hard to derive/select the software and hardware components to support them. Challenges and economical interests relating to these systems are numerous. QoS doesn’t only mean the improvement of performance (e.g. achieve better response time). Rather it implies many functions/activities for resources management (e.g. bandwidth and CPU) in order to fulfill different levels (deterministic or statistic) of QoS requirements under given assumptions on the user application behavior and on the underlying system support (type of network, type of software architecture…). Our topics of interest mainly include:

Quality of service in networks for the support of real-time and multimedia applications:

Validation of real-time and embedded applications:

Model for QoS specification and handling

To contribute to QoS-aware network design, we proposed a semi-formal framework platform independent with three objectives: clarifying the QoS notion, enabling network modeling with QoS-component-oriented approach, and enabling validation of models. The proposed framework enables modeling (with UML diagrams) the network and its internal components with their characteristics and their QoS requirements at different abstraction levels. To reduce the horizontal complexity (i.e. complexity depending on the aspect representation at a given abstraction level), we divide the aspects into: functional, architectural and qualitative aspects. For vertical complexity reduction (i.e. complexity depending on the abstraction level) we propose four abstraction levels: User level, Inter-domain level, Intra-domain level, and Equipment level. Our QoS specification language (QSL) enables specifying the QoS structure (QoS characteristics, units, application domains, component combination properties…) used in modeling approach. It also enables manipulate specified concepts/elements (either by assigning values to QoS elements or by comparing or composing these elements, or also by expressing QoS constraints). QSL also provides capabilities to adapt relationships that may be established between model elements. Finally, QSL enables representation of QoS contracts or SLA (Service level agreements).

Computation of communication delay bounds

One of the key issues to provide QoS guarantees in networks is packet scheduling (i.e. how to schedule packet transmissions at routers in such a way that QoS constraints of flows are met?). In the scheduling domain, CBQ (Class-based queuing) is considered as the most promising technique to provide QoS guarantees at large scale (i.e. for large networks and/or high number of flows). We focused on the performance of CBQ (computation of delay bound when heterogeneous flows are considered). Performance analysis may be achieved either by a stochastic approach (for a statistical analysis) or by a deterministic approach (for worst case analysis). We chose Network calculus, which provides a powerful theory for the analysis of servers in general and the routers in particular. Our contribution consists in, on one hand, defining a framework for the application of network calculus to CBQ and, on the other hand, the computation of theoretic bounds of communication delays that may be provided by CBQ-based routers. We also proposed guidelines for selecting CBQ parameters in order to increase performances according to utilization context. Finally, we were interested in CBQ deployment over wireless networks in general and IEEE 802.11 access points in particular. Obtained results show that the characteristics (particularly the variable link capacities) of wireless networks make it hard (or even impossible) to deploy CBQ in wireless networks, because CBQ was designed for wired networks where the capacity of link is fix.

Reactive routing protocols for bandwidth optimization and delay guarantees in MANETs

Owing to their self-configuring capabilities, MANETs (mobile ad hoc networks) may be easily deployed in many application domains such embedded systems (e.g. for traffic information exchange between vehicles on a high way), emergency operations (in case of accidents, earthquake, flood…) or military operations on the battle field. All such applications on one hand have no infrastructure and often have QoS requirements (in particular delays of critical messages should be kept under some fixed bounds) on the other hand. In general, MANETs are continuously changing (in topology because of node movements, in link capacities and signal quality because of interferences), which makes it difficult (or even impossible) to elaborate a global network state sufficiently consistent and stable to enable nodes know (with some level of accuracy) the resources (bandwidth and memory capacities) available at all the nodes to appropriately decide whether or not to start new flows. We proposed multiple routing protocols (with appropriate weight functions) to select paths optimizing bandwidth consumption. In existing routing protocols providing QoS guarantees (in terms of delay and bandwidth), path selection is based on the path length (i.e. the shortest path meeting the QoS requirements is selected). We showed that such a selection strategy may lead to bandwidth wasting, because whenever a flow is admitted at a node, the packets of such a flow impact all the neighbors of this node preventing them sending or receiving during transmission of these packets. Compared to existing QoS-aware routing protocols, our protocols consider the neighboring of each selected node to form a path. We also proposed a framework to compute the number of collisions and the impact of such collisions on network throughput. Solutions were proposed to reduce routing protocol cost (in packets) based on limiting the number of route request packets (route request packets are sent only to the nodes the most likely to reach the destination). Our routing protocols are extensions to the well known and used AODV protocol.

QoS mapping in TDMA-based wireless sensor networks

Wireless sensors take advantage from both being wireless and tiny, allowing them to be deployed nearly anywhere: in clothes, vehicles, streets, forests, etc. In order to realize “smart” environments, sensors should be able to communicate and collaborate, and perform potential interactions with their environment, which is done through wireless networks called Wireless Sensor Networks (WSN). Due to their small size, sensors suffer from limited resources like energy, computing power, and memory. Therefore, most of the scientific efforts are aiming to cope with the energy consumption issue, while leaving some equally crucial issues unexplored, like the QoS support. Like any distributed system user, the WSN user may have also QoS requirements that need to be met, otherwise the sensor-measured information becomes useless. In a WSN-based video surveillance application for example, the user should be able to demand a certain video resolution, along with some data freshness and image size. These user level QoS requirements should be mapped to network level QoS requirements like bandwidth and delay in order to perform the suitable reservations and to check if the application would be feasible or not. This process of mapping QoS requirements from level to level is known as QoS mapping. Our work focuses mainly on the QoS mapping process in TDMA-based networks, which are based on hierarchical clustered topologies, which allow the deployment of dense networks, making them more scalable and easier to manage. One of the natural issues that emerge in this kind of dense networks is the interference problem. Clustering has also other benefits like allocating the same time slots to non interfering nodes (i.e. nodes located at non overlapping clusters) leading to an optimized superframe length, which we took into consideration in our work.

Generic architecture for processing location-dependent queries under real-time constraints

Recent developments in wireless network technologies and localization systems such as GPS contributed to the emergence of numerous location-based services and applications (including vehicle guiding and tracking, assistance to emergency teams to find ambulances and available surgical tables in hospitals and clinics). We collaborated with SAMU 31 (medical emergency service of Haute Garonne) to propose a generic architecture (DBMS-independent) for processing requests (on data stored in database) sent by mobile vehicles and requiring responses (or results) under bounded delays. Architecture components have been defined: request analysis (client requests are expressed in a language we proposed), translation of location-aware requests into spatial requests, calculation of the space for objects searching depending on the mobility parameters (speed, orientation….) of the request client, estimate of server response time, estimate of communication time, and estimate of remaining time before the results (which will be sent to the client) become obsolete (because they will be sent too late to a client who is moving), and request scheduling before submitting request to the underlying DBMS (e.g. spatial Oracle). We proposed original rules to automatically derive search space and timing constraints of requests. Finally, our architecture was used by AKKA technologies to develop an operational prototype tested by SAMU31 to partially automate the management of their operational means (ambulances, helicopters…). This work was achieved in collaboration with Pyramide team at IRIT.

Verification method for avionic systems

Safety makes certification of avionic systems a mandatory task. Formal verification is one of the key techniques to achieve system certification. A system should be formally validated and then certified. In this context, we proposed a method for of the specification and validation distributed avionic systems, a method based on timing model checking and abstraction techniques. In our approach, an avionic system is handled as a set of functions interacting via a communication network. The proposed model captures the communications between functions and the timing constraints that should be met by these communications. Taking into account the networks the most likely to be used in the future/new aircrafts (particularly switched Ethernet), communications inside an avionic system may be expressed by the local performance of resources (waiting delay in queues of switches in particular). To enable a model checking based verification, a translation mechanism to derive timing automata is defined. Since model checking based verification suffers combinatory explosion, we chose to adapt an abstract communication model based on timing channels. The proposed framework enables the validation of consistency of given abstractions. The proposed model is defined at two levels: one based on messages and the other on events. Message level enables the specification of the behavior of each function. The global system dynamics is captured via the event level. The network is modeled by the parallel composition of the paths traversing each switch.

Real-time system validation based on polyhedral domains

The main motivation of our work is that some values of parameters of tasks (which are components of a real-time application) may be unknown at the early stage of application design and the designer needs to gradually validate the application (i.e. validate the application as the parameter values become available) or he/she needs to know for which task parameter values the application may be valid (i.e. the timing constraints will be met). We propose a validation approach that may be used as a guide/help for application designer by providing the value bounds for some task parameters. To handle constraints of systems where the information related to task parameters are partial, we use polyhedrons and associate a polyhydric dimension (thus an interval of values) with each system parameter. The information relating to parameters and constraints (such worst execution time, task release time and deadline) enable refine (derive) the polyhedron structure. As the polyhedrons cannot be used to represent constraint conjunctions, we use polyhydric domains to represent conjunction and disjunction constraints. Our validation method enable handling the commonly specified task constraints: task deadlines, resource sharing, task precedence, and timing portioning of tasks. Our method has a great advantage, it guarantees validation process termination (i.e. it is decidable).