Abstract

In this report, we study the problem of optimizing the throughput of applications for heterogeneous platforms subject to failures. The considered applications are composed of a sequence of consecutive tasks linked as a linear graph (pipeline), with a type associated to each task. The challenge is to specialize the machines of a target platform to process only one task type, given that every machine is able to process all the types before being specialized, to avoid costly context or setup changes. Each instance can thus be performed by any machine specialized in its type and the workload of the system can be shared among a set of specialized machines. For identical machines, we prove that an optimal solution can be computed in polynomial time. However, the problem becomes NP-hard when two machines can compute the same task type at different speeds. Several polynomial time heuristics are presented for the most realistic specialized settings. Experimental results show that the best heuristics obtain a good throughput, much better than the throughput obtained with a random mapping, and close to the optimal throughput in the particular cases on which the optimal throughput can be computed.; Dans ce rapport, nous étudions le problème de l'optimisation du débit d'applications de type pipeline dans un environnement hétérogène sujet à des pannes. Les applications sont constituées d'un ensemble de tâches consécu\\-tives typées et organisées selon une chaîne linéaire ou pipeline. Le but est ici de spécialiser les machines de la plate-forme d'exécution afin qu'elles ne traitent qu'un seul type de tâches, sachant qu'au départ elles peuvent exécuter tous les types. Cela permet d'éviter des reconfigurations coûteuses entre tâches de types différents sur une même machine. Ainsi, les instances d'une même tâche peuvent être distribuées sur plusieurs machines spécialisées pour le type de cette tâche, ce qui permet une répartition de la charge du système sur un ensemble de machines spécialisées. Lorsque la plate-forme est composée de machines identiques, nous prouvons qu'une solution optimale peut être trouvée en temps polynomial. Par contre, le problème devient NP-complet dès lors que deux machines peuvent traiter une même tâche à des vitesses différentes. Ce faisant, plusieurs heuristiques sont présentées dans le cas le plus réaliste d'un système spécialisé. Les résultats expérimentaux montrent que les meilleures heuristiques obtiennent de bons résultats en terme de débit, meilleurs qu'avec une allocation aléatoire, et que les débits atteints sont très proches des débits optimaux dans les cas particuliers pour lesquels une solution optimale peut être calculée. Document type: Part of book or chapter of book

Abstract

Part 6: New Testing Methods; International audience; In this paper, we focus on Mobile Ad-hoc Networks (MANETs) with non-uniform node density distribution such as Vehicular Ad-hoc Networks (VANETs) and Delay Tolerant Networks (DTNs), and propose a technique for protocol testing and performance evaluation. In such MANETs, node density varies depending on locations and time, and it dynamically changes every moment. In the proposed method, we designate node density distributions and their dynamic variations in a target area. Then, we construct a graph called TestEnvGraph where all node density distributions are treated as its nodes and they are connected by edges whose weights denote differences of two node density distributions. We specify a set of edges to be tested in the graph, formulate a problem for efficiently reproducing all the given node density distributions and their dynamic variations as a rural postman problem, find its solution and use it as the order of reproduction of designated node density distributions and their variations. Protocol testing is carried out by reproducing node density distributions in the derived order. We have designed and developed a method and its tool for mobility generation on MANETs, which can reproduce any designated node density distribution and its dynamic variations in a target area. From our experiments for a VANET protocol, we have shown that our method can give a similar trend in network throughput and packet loss rates compared with realistic trace based protocol testing. Document type: Part of book or chapter of book

Abstract

Traffic congestion is a major issue that plagues many urban road networks large and small. Traffic engineers are now leaning towards Intelligent Traffic Systems as many types of physical changes to road networks are costly or infeasible. Multi-Agent Systems (MAS) have become a popular paradigm for exploring intelligent solutions to traffic management problems. There are many MAS approaches to traffic management that utilise market mechanisms. In market-based approaches, drivers “pay” to use the roadways. However, a major issue with many of these solutions is that they require technology that, as yet, does not exist or is not widely available. For example, they rely on a special software agent that resides within the vehicle. This “vehicle agent” is responsible for participating in the market mechanism and communicating with the transportation infrastructure. In this paper, an auction-based traffic controller is proposed which exploits all the benefits of market mechanisms without the need for a vehicle agent. Experimental results show that such a controller is better at reducing delay and increasing throughput in a simulated city, as compared to fixed-time signal controllers. Document type: Part of book or chapter of book

Abstract

The problem of finding multi-constrained paths has been addressed by several QoS routing algorithms. While they generally satisfy the application requirements, they often do not consider the perspective of service providers. Service providers aim at maximizing the throughput and the number of accepted requests. These goals have been addressed by traffic engineering algorithms considering bandwidth as the sole application requirement. We propose a proper length function for an existing QoS routing algorithm (SAMCRA) that attempts to optimize network utilization while still offering QoS guarantees. This paper presents a comparison between several proposed algorithms via simulation studies. The simulations show that SAMCRA with a proper length performs similarly or even better than the best among the other algorithms and it has a fast running time. Document type: Part of book or chapter of book

Abstract

This paper describes two traffic engineering techniques for implementing proportional differentiated services based on Multiprotocol Label Switching constraint based routing. Both use a dynamic bandwidth allocation scheme to modify the bandwidth reserved by each traffic class according to the current network load. The first scheme uses an adaptive algorithm that qualitatively determines the required average throughput per source for each class and moves bandwidth between classes for each path as necessary. The second scheme mathematically divides the existing bandwidth through the traffic classes for each path. The quality of service that users get with both techniques is assessed by simulation and compared with a fixed bandwidth allocation scheme. 5th IFIP International Conference on Network Control & Engineering for QoS, Security and Mobility Red de Universidades con Carreras en Informática (RedUNCI) Document type: Part of book or chapter of book

Abstract

International audience; The experimental evaluation of wireless and mobile networks is a challenge that rarely substitutes simulation in research works. This statement is even more evident in vehicular communications, due to the equipment and effort needed to obtain significant and realistic results. In this paper, key issues in vehicular experimental evaluation are analyzed by an evaluation tool called AnaVANET, especially designed for assessing the performance of vehicular networks. This software processes the output of well-known testing tools such as ping or iperf, together with navigation information, to generate geo-aware performance figures of merit both in numeric and graphical forms. Its main analysis capabilities are used to validate the good performance in terms of delay, packet delivery ratio and throughput of NEMO, when using a road-side segment based on IPv6 GeoNetworking. Document type: Part of book or chapter of book

Abstract

KARYON, a kernel-based architecture for safety-critical control, is a European project that proposes a new perspective to improve performance of smart vehicle coordination focusing on Advanced Driver Assistance Systems (ADASs) and Unmanned Aerial Systems (UAS). The key objective is to provide system solutions for predictable and safe coordination of smart vehicles that autonomously cooperate and interact in an open and inherently uncertain environment. Currently, these systems are not allowed to operate on the public roads or in the air space, as the risk of causing severe damage cannot be excluded with sufficient certainty. The impact of the project is two-fold; it will provide improved vehicle density without driver involvement and increased traffic throughput to maintain mobility without a need to build new traffic infrastructures. The results will improve interaction in cooperation scenarios while preserving safety and assessing it according to standards. The prospective project results include self-stabilizing algorithms for vehicle coordination, communication and synchronization. In addition, we aim at showing that the safety kernel can be designed to be a self-stabilizing one. Document type: Part of book or chapter of book

Abstract

This paper uses analysis and experiments to study the minimal buffering requirements of congestion controlled multimedia applications. Applications in the Internet must use congestion control protocols, which vary transmission rates according to network conditions. To produce a smooth perceptual quality, multimedia applications use buffering and rate adaptations to compensate these rate oscillations. While several adaptation policies are available, they require different amounts of buffering at end-hosts. We study the relationship between buffering requirements and adaptation policies. In particular, we focus on a widely pursued policy that adapts an application's sending rate exactly to the average available bandwidth to maximize throughput. Under this adaptation policy, at least a minimal amount of buffering is required to smooth the rate oscillation inherent in congestion control, and we view this minimal buffering requirement as a cost of maximizing throughput. We derive the minimal buffering requirement for this policy assuming that applications use an additive-increase-and-multiplicative-decrease (AIMD) algorithm for congestion control. The result shows the relationship between parameters of AIMD algorithms and the delay cost. We show that the buffering requirement is proportional to the parameters of the AIMD algorithm and quadratic to the application's sending rate and round-trip-time. We verify this relationship through experiments. Our results indicate that adaptation policies that maximize throughput are not suitable for interactive applications with high bit rates or long round-trip-times. Document type: Part of book or chapter of book

Abstract

International audience; Mapping applications onto parallel platforms is a challenging problem, even for simple application patterns such as pipeline or fork graphs. Several antagonist criteria should be optimized for workflow applications, such as throughput and latency (or a combination). In this paper, we consider a simplified model with no communication cost, and we provide an exhaustive list of complexity results for different problem instances. Pipeline or fork stages can be replicated in order to increase the throughput by sending consecutive data sets onto different processors. In some cases, stages can also be data-parallelized, i.e. the computation of one single data set is shared between several processors. This leads to a decrease of the latency and an increase of the throughput. Some instances of this simple model are shown to be NP-hard, thereby exposing the inherent complexity of the mapping problem. We provide polynomial algorithms for other problem instances. Altogether, we provide solid theoretical foundations for the study of mono-criterion or bi-criteria mapping optimization problems. Document type: Report