This article proposes to use an RNA graph similarity metric, based on the MCES resolution problem, to compare the occurrences of specific complex motifs in RNA graphs, according to their context represented as subgraph. We rely on a new modeling by graphs of these contexts, at two different levels of granularity, and obtain a classification of these graphs, which is consistent with the RNA 3D structure. RNA many non-translational functions, as a ribozyme, riboswitch, or ribosome, require complex structures. Those are composed of a rigid skeleton, a set of canonical interactions called the secondary structure. Decades of experimental and theoretical work have produced precise thermodynamic parameters and efficient algorithms to predict, from sequence, the secondary structure of RNA molecules. On top of the skeleton, the nucleotides form an intricate network of interactions that are not captured by present thermodynamic models. This network has been shown to be composed of modular motifs, that are linked to function, and have been leveraged for better prediction and design. A peculiar subclass of complex structural motifs are those connecting RNA regions far away in the secondary structure. They are crucial to predict since they determine the global shape of the molecule, therefore important for the function. In this paper, we show by using our graph approach that the context is important for the formation of conserved complex structural motifs. We furthermore show that a natural classification of structural variants of the motifs emerges from their context. We explore the cases of three known motif families and we exhibit their experimentally emerging classification.

Reinforcement learning is a commonly used technique in the field of traffic signal control. By iteratively testing actions given the current network state, a traffic signal agent gradually learns to optimally control traffic lights given the traffic situation at hand. While they usually outperform traditional control systems in the literature, these methods have to first go through an exploration phase where they test different actions in a trial-and-error fashion. The nature of reinforcement learning methods hence causes unstable performances and high computational costs. In order to limit the costs linked to this exploration phase, we propose a bootstrapping method that reduces the computation time needed for learning-based traffic control methods to reach acceptable performance levels. Our method models lanes of the road network as queues, and derives results on the average service time of vehicles at the intersection level in order to estimate the agent's policy. The performance of our bootstrapping method is then compared to a more traditional Q-Learning method using the SUMO simulator. Simulation results show that bootstrapping alleviates both of these issues by immediately reaching acceptable performance levels by quickly training the agent without any direct interaction with the simulation environment.

Game theory is a powerful tool that has recently been used in networks to improve the end users' quality of experience (e.g. decreased response time, higher delivery rate). In this paper, we propose to use game theory in the context of Content Delivery Networks (CDNs) to organize video contents into clusters having similar request profiles. The popularity of each content in the cluster can be determined from the popularity of the representative of the cluster and used to store the most popular contents close to end users. A group of experts and a decision-maker predict the popularity of the representative of the cluster. This considerably reduces the number of experts used. More precisely, we model the clustering problem as a hedonic coalition formation game where each coalition represents a cluster. The coalition game converges to a stable partition representing a solution of the problem considered. We compare the results of this approach with the clustering obtained by the K-means algorithm. We evaluate the impact of the content profile observation window considered to establish the clustering. We also evaluate the complexity of the proposed algorithm. Simulation results are obtained on traces of a real CDN. Finally, we extend the proposed approach to model an on-line clustering reflecting the CDN dynamics in terms of proposed contents and contents solicitations.

Urban Parking is a problem that costs time and energy. That is why intelligent parking is a field of research growing very quickly. In a city where no sensor infrastructure within each place is deployed but only a counting system at every intersection is available, we show that it still possible to propose an efficient method that determines an itinerary that minimizes the expected time to find an available parking place. For this, we first model the urban area by a graph. Then, we implement a learning algorithm that uses a reinforcement learning method. In this model, each agent modeling an intersection, learns the best next street portion. At each step, all the decisions taken by the agents generate an itinerary whose expectation time is the basis for updating the parameters of learning. The execution times and performances of the learning algorithm are compared with those of a method that constructs step by step the itinerary by choosing the next segment with an evaluation of the future expectation time within this segment. We evaluate the performance of the learning algorithm by realistic simulations. The simulation data are extracted from the map of Versailles.

MOTIVATION: Predicting the 3D structure of RNA molecules is a key feature towards predicting their functions. Methods which work at atomic or nucleotide level are not suitable for large molecules. In these cases, coarse-grained prediction methods aim to predict a shape which could be refined later by using more precise methods on smaller parts of the molecule. RESULTS: We developed a complete method for sampling 3D RNA structure at a coarse-grained model, taking a secondary structure as input. One of the novelties of our method is that a second step extracts two best possible structures close to the native, from a set of possible structures. Although our method benefits from the first version of GARN, some of the main features on GARN2 are very different. GARN2 is much faster than the previous version and than the well-known methods of the state-of-art. Our experiments show that GARN2 can also provide better structures than the other state-of-the-art methods. AVAILABILITY AND IMPLEMENTATION: GARN2 is written in Java. It is freely distributed and available at http://garn.lri.fr/. CONTACT: [email protected] or [email protected]. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Machine learning techniques can be used to improve the quality of experience for the end users of Content Delivery Networks (CDNs). In a CDN, the most popular video contents are cached near the end-users in order to minimize the contents delivery latency. The idea developed hereafter consists in using prediction techniques to evaluate the future popularity of video contents in order to decide which should cached. We consider various prediction methods, called experts, coming from different fields (e.g. statistics, control theory). To evaluate the accuracy of the experts' popularity predictions, we assess these experts according to three criteria: cumulated loss, maximum instantaneous loss and best ranking. We also show the importance of a decision maker, called forecaster, that predicts the popularity based on the predictions of selection of several experts. The forecaster based on the best K experts outperforms in terms of cumulated loss the individual experts' predictions and those of the forecaster based on only one expert, even if this expert varies over time.

In Content Delivery Networks (CDNs), knowing the popularity of video content helps the manager to take efficient decisions about which video content should be cached near the end users and also about the duplication degree of each video to satisfy the end user Quality of Experience. This paper focuses on predicting the popularity of video content, in terms of the number of requests. For that purpose, different software entities, called experts, compute the popularity value of each video content. Each expert uses its own prediction method. The accuracy of expert's prediction is evaluated by a loss function as the discrepancy between the prediction value and the real number of requests. We use real traces extracted from YouTube to compare different prediction methods and determine the best tuning of their parameters. The goal is to find the best trade-off between complexity and accuracy of the prediction methods used. Finally, we apply these prediction methods to caching. Prediction methods are compared in terms of cache Hit Ratio and Update Ratio with the well-known LFU caching strategy.

Content delivery networks (CDNs) face a large and continuously increasing number of users solicitations for video contents. In this paper, we focus on the prediction of popularity evolution of video contents. Based on the observation of past solicitations of individual video contents, individual future solicitations are predicted. We compare different prediction strategies: SES, DES and Basic. The best tuning of each strategy is determined, depending on the considered phase of the solicitation curve. Since DES and Basic experts outperform the SES expert, our method combines DES and Basic experts to predict the number of solicitations within a phase and automatically detect the phase changes, respectively. This self-learning and prediction method can be applied to optimize resources allocation in service oriented architectures and self-adaptive networks, more precisely for the CDN cache nodes management.

We present our work on the dimensioning of a packet-switching wavelength division multiplexing ring in order to reduce its infrastructure (capital expenditure) cost. We study a new all-optical architecture: the packed optical add-drop multiplexer (POADM). We aim to minimize the overall cost of the network by reducing the number of indispensable devices in the nodes and the number of required wavelengths. We formalize the packing problems underlying the ring dimensioning. The elements to be packed are made up of transmissions that share the same destination. We assume that elements can be cut before being packed into boxes. We furnish a complete theoretical analysis of the complexity and approximability of these problems. We define also several measures of quality for a cut and provide an optimal cutting strategy, according to these measures. Our subsequent contribution is a heuristic solution that solves the bi-criteria packing problem (the number of boxes and the number of cuts are minimized simultaneously). The exhaustive numerical results of this heuristic algorithm come next. We rely on our optimal cutting strategy to appraise the efficiency of other strategies. We also adapt the only existing POADM dimensioning algorithm, more restrictive than ours, and we confront it with our solution. The analysis of results allows us to provide network design guidelines to perform the dimensioning in the most efficient way.

Bandwidth sharing paradigm constitutes an incentive solution for the serious capacity management problem faced by operators as femtocells owners are able to offer a QoS guaranteed network access to mobile users in their femtocell coverage. In this paper, we consider a technico-economic bandwidth sharing model based on a reinforcement learning algorithm. Because such a model does not allow the convergence of the learning algorithm, due to the small size of the femtocells, the mobile users velocity and, more importantly, the randomness of their arrivals, we propose to use a mobility prediction approach based on the analysis of movements history of the mobile users. Knowing the next visited cell in advance provides more time to mobile user to negotiate with the access provider and to generate synchronized resource reservation requests that maximize the gain of the access provider.

We present a new approach for the prediction of the coarse-grain 3D structure of RNA molecules. We model a molecule as being made of helices and junctions. Those junctions are classified into topological families that determine their preferred 3D shapes. All the parts of the molecule are then allowed to establish long-distance contacts that induce a 3D folding of the molecule. An algorithm relying on game theory is proposed to discover such long-distance contacts that allow the molecule to reach a Nash equilibrium. As reported by our experiments, this approach allows one to predict the global shape of large molecules of several hundreds of nucleotides that are out of reach of the state-of-the-art methods.

We propose in this paper a mobility prediction model based on the notions of local and global mobile-user profiles. The local profiles are associated with a mobile user and correspond to its frequent and similar movements, whereas the global profiles match with the frequent and similar movements of the majority of users in the covered area. We consider the LTE network architecture with possible deployment of femtocells. The prediction model combines two complementary algorithms: the global profiles-based algorithm and the local profiles-based one. The former is implemented in the enhanced Node B and the home enhanced Node B and the latter works at the user terminal level. An algorithmic approach is used to identify such local and global profiles from real cellular network datasets and we show how to use them for an efficient mobility prediction. Simulation results show that our approach is significantly efficient in predicting both random and regular movements.

In this paper we propose a new approach for mobility prediction. It is based on the notion of mobile-user profile which corresponds to frequent similar movements of a user. Such a profile is defined, in the neighbourhood graph of a cellular network, as a set of similar sequences of crossed cells from one source cell to one destination cell. We propose an algorithmic approach to identify such profiles from real cellular network datasets and we show how to use them for an efficient mobility prediction. Simulation results show that the global approach is significantly efficient in predicting both random and regular movements.

Recent developments in optical communications have led to the creation of large scale optical networks allowing its users to run distributed applications with high QoS requirements. In this context, this paper focuses on a strategy of reservation of temporal virtualized resources in an high bandwidth optical network for service composition. In this strategy, the service composition requirements are modeled by a specific workflow graph with constraints. To satisfy such demands, the workflow graph is embedded in a graph modeling the network in which the availability of resources is scheduled in consecutive equal time periods. We first present the models of workflow and network graphs we use and the theoretical problems we focus on. Then, we describe an online embedding algorithm and we evaluate its performances on various demand scenarii.

In this paper we propose PARINET, a new access method to efficiently retrieve the trajectories of objects moving in networks. The structure of PARINET is based on a combination of graph partitioning and a set of composite B+-tree local indexes. PARINET is designed for historical data and relies on the distribution of the data over the network as for historical data, the data distribution is known in advance. Because the network can be modeled using graphs, the partitioning of the trajectory data is based on graph partitioning theory and can be tuned for a given query load. The data in each partition is indexed on the time component using B+-trees. We study different types of queries, and provide an optimal configuration for several scenarios. PARINET can easily be integrated into any RDBMS, which is an essential asset particularly for industrial or commercial applications. The experimental evaluation under an off-the-shelf DBMS shows that PARINET is robust. It also significantly outperforms both MON-tree and another R-tree based access method which are the reference indexing techniques for in-network trajectory databases.

This paper focuses on QoS guarantees in an interdomain selfish network where each domain may sell QoS guarantees for its transit traffic. The main objective of the paper is to evaluate the benefit for some of these domains to develop together a privileged partnership in terms of economic alliance. This alliance permits the members to share their local knowledge of the network and to exchange some traffic network services. After defining the alliance model and the way each domain may use it to obtain better QoS guarantees, we analyse by simulation on realistic generated topologies the impact of such alliances on the QoS requests satisfaction.

In this paper, a new mobility prediction model is investigated. We consider a two nodes (enhanced gateway and base station) mobile network architecture based on intelligent IP framework. The proposed model is based on two complementary algorithms for mobility prediction: a global prediction algorithm and a local one. While the former is implemented in the gateway, the latter is used by the base station. At the gateway level, the algorithm detects the regular movements of the mobile users whereas the algorithm, at the base station level, tracks more closely, within the cell, the movements of the mobile users. Our prediction model gives significant results in both mobility conditions, regular and random movements.

One of the main challenges in all-IP networks is the development of suitable mobility solution. Mobile IP (MIP) presents the standard protocol used to support IP mobility. However, MIP is inadequate for real-time applications and inter-domain mobility (when a mobile node performs handover between two autonomous systems (AS)). In this paper, we propose an efficient approach to manage inter-domain handover in attempt to reduce the delay variation which cause service disruption. We propose an algorithm to select routes connecting two ASs such as the delay variation is minimal. First, we prove that the corresponding graph problem is NP-complete. Then, we propose a global strategy to find routes for each source-destination pair of ASs giving a small delay variation. Finally, we measured by simulation the efficiency of this strategy in comparison with its algorithmic time complexity.

In this paper, we deal with 2-rearrangeable graphs, that is, graphs in which every permutation can be routed in two steps, such that each packet moves on a walk of length 2 without vertex-contention. We give necessary and sufficient conditions for a graph to be 2-rearrangeable. We end by proposing a construction of k-rearrangeable graphs, where k ≥ 2. © 1998 John Wiley & Sons, Inc. Networks 31: 239–247, 1998

Given a network of processors, a structured communication problem consists to route a communication pattern known in advance. Structured communication problems appear frequently in parallel computing. Hence, communication libraries (e.g, PVM or MPI) generally include a specific access to procedures solving the most common problems of this type. A standard communication model assumes that information proceeds by a sequence of calls between neighboring nodes of the network, and that each node is allowed to call at most one neighbor at a time. In this context, most of the decision problems corresponding to the usual structured communication problems have been shown to be NP-complete. Therefore, several approximation algorithms have been proposed to solve specific problems. Each of these algorithms is dedicated to a particular problem. In this paper, we present a high level method which can be used to derive approximation algorithms for many different structured communication problems on ...