Book Series
2009 EN
Vincent Reinhard · Joanna Tomasik · Dominique Barth
+1 more
The CARRIOCAS project aims to guarantee QoS connectivity services to distributed applications in a Telecom carrier network. A large number of these applications (for example video applications) use a multicast service packet delivery. Multicast which minimizes the total used bandwidth in the MPLS network has become an important subject. We study multicast routing in the network where only some routers can duplicate packets. We prove that the construction of a multicast tree minimizing the bandwidth used in such a network is a NP -complete problem and we propose an heuristic algorithm to solve it. We evaluate the performance of the heuristic in terms of total bandwidth used by the multicast for different network sizes.
Springer Science+Business Media
Book Series
2009 EN
Guillaume Rizk · Dominique Lavenier
Many bioinformatics studies require the analysis of RNA or DNA structures. More specifically, extensive work is done to elaborate efficient algorithms able to predict the 2-D folding structures of RNA or DNA sequences. However, the high computational complexity of the algorithms, combined with the rapid increase of genomic data, triggers the need of faster methods. Current approaches focus on parallelizing these algorithms on multiprocessor systems or on clusters, yielding to good performance but at a relatively high cost. Here, we explore the use of computer graphics hardware to speed up these algorithms which, theoretically, provide both high performance and low cost. We use the CUDA programming language to harness the power of NVIDIA graphic cards for general computation with a C-like environment. Performances on recent graphic cards achieve a ×17 speed-up.
Springer Science+Business Media
Book Series
2009 EN
Dominique Aubert · Mehdi Amini · Romaric David
We present a particle-mesh N-body integrator running on GPU using CUDA. Relying on a grid-based description of the gravitational potential, it can simulate the evolution of self-interacting `stars' in order to model e.g. galaxies. All the steps of the application have been ported on the GPU , namely 1/ an histogramming algorithm with CUDPP, 2/ of the resolution of the Poisson equation by means of FFT with CUFFT and multi-grid relaxation, 3/ of an optimized finite difference scheme to compute the accelerations of stars and 4/ of an update procedure for positions and velocities. We present several tests at different resolution, and reach a speedup from 2 to 50 depending on the resolution and on the test case.
Springer Science+Business Media
Book Series
2009 EN
Iksoon Hwang · Mounir Lallali · Ana Cavalli
+1 more
International audienceIn this paper, we present the modeling, validation, and verification of an industrial protocol for constraint-based path computation, called PCEP. From the PCEP specification defined by IETF, we divide the functionalities of PCEP into two parts: application and protocol. The protocol part of PCEP is then described in the IF language which is based on communicating timed automata. A number of basic requirements are identified from the PCEP specification and then described as properties in the IF language. Based on these properties, the validation and verification of the formal specification are carried out using the IF toolset. Test cases are generated by using an automatic test generation tool, called TestGen-IF, which uses partial state space exploration guided by test purposes. As a result of the modeling, validation, and verification, some errors and ambiguities are found in the PCEP specification. Also a number of test cases are obtained which will be used for testing implementation
Springer Science+Business Media
Book Series
2009 EN
Dominique Duval · Rachid Echahed · Frédéric Prost
International audienceWe address the problem of cyclic termgraph rewriting. We propose a new framework where rewrite rules are tuples of the form $(L,R,\tau,\sigma)$ such that $L$ and $R$ are termgraphs representing the left-hand and the right-hand sides of the rule, $\tau$ is a mapping from the nodes of $L$ to those of $R$ and $\sigma$ is a partial function from nodes of $R$ to nodes of $L$. $\tau$ describes how incident edges of the nodes in $L$ are connected in $R$. $\tau$ is not required to be a graph morphism as in classical algebraic approaches of graph transformation. The role of $\sigma$ is to indicate the parts of $L$ to be cloned (copied). Furthermore, we introduce a new notion of \emph{cloning pushout} and define rewrite steps as cloning pushouts in a given category. Among the features of the proposed rewrite systems, we quote the ability to perform local and global redirection of pointers, addition and deletion of nodes as well as cloning and collapsing substructures
Springer Science+Business Media
Book Series
2009 EN
Mathilde Bouvel · Cédric Chauve · Marni Mishna
+1 more
International audienceA sequence of reversals that takes a signed permutation to the identity is perfect if at no step a common interval is broken. Determining a parsimonious perfect sequence of reversals that sorts a signed permutation is NP-hard. Here we show that, despite this worst-case analysis, with probability one, sorting can be done in polynomial time. Further, we find asymptotic expressions for the average length and number of reversals in commuting permutations, an interesting sub-class of signed permutations
Springer Science+Business Media
Book Series
2009 EN
Marcelo Morandini · Walter Abreu Cybis · Dominique L. Scapin
This paper presents current actions, results and perspectives concerning the development of the ErgoCoIn approach, which allows non expert inspectors to conduct ergonomic inspections of e-commerce web sites. An environment supporting inspections based on this approach was designed and a tool is being developed in order to accomplish its validation plan. Besides this validation, the actions to be undertaken will allow us to analyze the task of applying checklists and specify an inspection support environment especially fitted for that. This is of great importance as this environment is intended to be an open web service supporting ergonomic inspections of web sites from different domains. A wiki environment for this tool development is also being proposed.
Springer Science+Business Media
Book Series
2009 EN
Sybille Caffiau · Patrick Girard · Laurent Guittet
+1 more
In order to design interactive applications, the first step is usually the definition of user needs. While performing this step, activities may be modeled using task models. Some task model components express scheduling information that describes the task dynamics. According to a model-based approach, the dynamics of applications (i.e.: the dialog) can be formalized using a dialog model. Several approaches seek to exploit the task model information to perform the dialog model. This paper aims to show that the use of the hierarchical dialog model facilitates its design according to task model information during the whole iterative design process.
Springer Science+Business Media
Book Series
2009 EN
Dominique Brunet · Edward R. Vrscay · Zhou Wang
State-of-the-art image denoising algorithms attempt to recover natural image signals from their noisy observations, such that the statistics of the denoised image follow the statistical regularities of natural images. One aspect generally missing in these approaches is that the properties of the residual image (defined as the difference between the noisy observation and the denoised image) have not been well exploited. Here we demonstrate the usefulness of residual images in image denoising. In particular, we show that well-known full-reference image quality measures such as the mean-squared-error and the structural similarity index can be estimated from the residual image without the reference image. We also propose a procedure that has the potential to enhance the image quality of given image denoising algorithms.
Springer Science+Business Media
Book Series
2009 EN
Markus Rückert · Dominique Schröder
Aggregate signatures provide bandwidth-saving aggregation of ordinary signatures. We present the first unrestricted instantiation without random oracles, based on the Boneh-Silverberg signature scheme. Moreover, our construction yields a multisignature scheme where a single message is signed by a number of signers. Our second result is an application to verifiably encrypted signatures. There, signers encrypt their signature under the public key of a trusted third party and output a proof that the signature is inside. Upon dispute between signer and verifier, the trusted third party is able to recover the signature. These schemes are provably secure in the standard model.
Springer Science+Business Media