Un des problemes majeurs dans le domaine des telecommunications est de construire des réseaux robustes qui puissent faire face a l'incertitude de la demande. Ayant l'architecture d'un réseau et un budget donne pour le problème d'allocation de la capacité, le but est d'identifier une capacité faisable, qui minimise le pire cas de demande insatisfaite. Premièrement, nous formulons l'incertitude de la demande comme un polytope engendre par un nombre fini de scénarios de la demande. Nous montrons que le problème peut se ramener a la minimisation d'une fonction convexe sur un polyèdre. Nous calculons alors une solution optimale par trois méthodes de plans sécants : Kelley, Elzinga & Moore et faisceaux. Ensuite, nous formulons l'incertitude comme un polyèdre décrit par un nombre fini d'inégalités linéaires, ce qui résulte en un problème considérablement plus difficile. Par conséquent, nous cherchons uniquement des bornes supérieures et inférieures. Quelques idées novatrices sont présentées et l'algorithme de type \Branch & Bound" de Falk & Soland est utilise afin de calculer le maximum d'une fonction convexe additive ; de plus, nous défifinissons une variante de cet algorithme, adaptée a notre situation particulière. Après avoir défini la capacité d'un réseau, l'étape suivante est de calculer le routage optimal dans ce réseau. Nous minimisons la congestion en utilisant comme objectif la fonction moyenne de retard de Kleinrock. Le problème résultant est convexe mais non-linaire et la fonction duale est la somme d'un terme polyédral et d'un terme différentiable. Afin de résoudre ce problème, nous implémentons un algorithme hybride base sur la relaxation Lagrangienne.

Pour répondre à une demande, toujours croissante, des services multimédias avancés et pour supporter la connectivité électronique partout sur la planète, le développement de systèmes multimédias à large bande ubiquitaires gagne un grand intérêt aux niveaux académique et industriel. Les réseaux satellitaires en général et les constellations de satellites Low Earth Orbit (LEO) plus particulièrement jouent un rôle essentiel dans le déploiement de ces systèmes. Les constellations de satellites LEO telles que "Iridium" ou "Iridium-NEXT" sont extrêmement coûteuses à déployer et à maintenir. Par conséquent, le prolongement de la durée de leur vie est d'une importance cruciale. Dans la partie principale de cette thèse, nous proposons différentes techniques pour prolonger la durée de vie des services satellitaire dans les constellations de satellites LEO. Dans de telles constellations, les satellites peuvent passer plus de 30% de leur temps sous l'ombre de la Terre, temps pendant lequel ils sont alimentés par des batteries. Bien que les batteries soient rechargées par l'énergie solaire, la profondeur de décharge qu'elles atteignent pendant l'éclipse affecte considérablement leur durée de vie et, par extension, la durée de vie des satellites eux-mêmes. Pour des batteries du même type que celles qui alimentent les satellites "Iridium" et "Iridium-NEXT", une augmentation de 15% de la profondeur de décharge peut pratiquement réduire leur durée de vie de moitié. En raison de la nature très uniforme et symétrique des constellations de satellites LEO, il peut y avoir de nombreux chemins alternatifs entre deux noeuds d'un réseau de satellites. La décision relative à l'envoi de données sur un de ces chemins a un effet important sur la durée de vie du réseau. Dans ce contexte, nous nous concentrons tout d'abord sur le routage et nous proposons deux nouvelles métriques de routage, "LASER" et "SLIM", qui tentent de trouver un équilibre entre la performance et la profondeur de décharge de la batterie dans les constellations de satellites LEO. Notre approche de base est de tirer parti du mouvement déterministe des satellites pour favoriser le routage du trafic sur les satellites exposés au soleil plutôt que sur les satellites éclipsés, diminuant ainsi la moyenne de la profondeur de décharge de la batterie, le tout sans pénaliser les performances. Avec l'utilisation d'une topologie LEO réelle et des requêtes de trafic, nous montrons que LASER et SLIM peuvent augmenter la durée de vie de la batterie de près de 75 % et 100 %, respectivement. Ensuite, nous nous occupons de la consolidation des ressources, un nouveau paradigme pour la réduction de la consommation d'énergie. Il consiste à avoir un sous-ensemble, soigneusement sélectionné, de liens réseau à mettre en veille, et à utiliser le reste des liens pour transporter la quantité requise du trafic. Cela est possible sans causer des perturbations majeures aux activités du réseau, étant donné que les réseaux de communication sont conçus pour des périodes de pic de trafic, avec de la redondance, et des ressources surestimées. Comme solutions à ces problèmes, nous proposons deux méthodes différentes pour effectuer la consolidation des ressources dans les réseaux LEO. Premièrement, nous proposons une métrique sensible au trafic pour quantifier la qualité d'une topologie frugal, nommée "MLU". Le problème étant NP-difficile soumis à un seuil "MLU" donné, nous présentons deux heuristiques, "BASIC" et "SNAP", qui représentent différents compromis en termes de performances et de simplicité. Deuxièmement, nous proposons une nouvelle métrique légère n'utilisant pas de trafic pour quantifier la qualité d'une topologie frugal, nommée "ADI". Après avoir montré que le problème de minimisation de la consommation d'énergie d'un réseau LEO soumis à un seuil donné d'ADI est NP-difficile, nous proposons une heuristique nommé "AvOId" à résoudre. / To meet an ever-growing demand for advanced multimedia services and to support electronic connectivity anywhere on the planet, development of ubiquitous broadband multimedia systems is gaining a huge interest at both academic and industry levels. Satellite networks in general and LEO satellite constellations in particular will play an essential role in the deployment of such systems. Therefore, as LEO satellite constellations like Iridium or IridiumNEXT are extremely expensive to deploy and maintain, extending their service lifetimes is of crucial importance. In the main part of this thesis, we propose different techniques for extending satellite service life in LEO satellite constellations. Satellites in such constellations can spend over 30% of their time under the earth’s umbra, time during which they are powered by batteries. While the batteries are recharged by solar energy, the Depth of Discharge (DoD) they reach during eclipse significantly affects their lifetime – and by extension, the service life of the satellites themselves. For batteries of the type that power Iridium and Iridium-NEXT satellites, a 15% increase to the DoD can practically cut their service lives in half. We first focus on routing and propose two new routing metrics – LASER and SLIM – that try to strike a balance between performance and battery DoD in LEO satellite constellations. Our basic approach is to leverage the deterministic movement of satellites for favoring routing traffic over satellites exposed to the sun as opposed to the eclipsed satellites, thereby decreasing the average battery DoD– all without taking a significant penalty in performance. Then, we deal with resource consolidation – a new paradigm for the reduction of the power consumption. It consists in having a carefully selected subset of network links entering a sleep state, and use the rest to transport the required amount of traffic. This possible without causing major disruptions to network activities. Since communication networks are designed over the peak traffic periods, and with redundancy and over-provisioned in mind. As a remedy to these issues, we propose two different methods to perform resource consolidation in LEO networks. First, we propose trafficaware metric for quantifiying the quality of a frugal topology, the Maximum Link Utilization (MLU). With the problem being NP-hard subject to a given MLU threshold, we introduce two heuristics, BASIC and SNAP, which represent different tradeoffs in terms of performance and simplicity. Second, we propose a new lightweight traffic-agnostic metric for quantifiying the quality of a frugal topology, the Adequacy Index (ADI). After showing that the problem of minimizing the power consumption of a LEO network subject to a given ADI threshold is NP-hard, we propose a heuristc named AvOId to solve it. We evaluate both forms of resource consolidation using realistic LEO topologies and traffic requests. The results show that the simple schemes we develop are almost double the satellite batteries lifetime. Following the green networking in LEO systems, the second part of this thesis focuses on extending the resource consolidation schemes to current wired networks. Indeed, the energy consumption of wired networks has been traditionally overlooked. Several studies exhibit that the traffic load of the routers only has a small influence on their energy consumption. Hence, the power consumption in networks is strongly related to the number of active network elements. In this context, we extend the traffic-agnostic metric, ADI, to the wired networks. We model the problem subject to ADI threshold as NP-hard. Then, we propose two polynomial time heuristics – ABStAIn and CuTBAck. Although ABStAIn and CuTBAck are traffic unaware, we assess their behavior under real traffic loads from 3 networks, demonstrating that their performance are comparable to the more complex traffic-aware solutions proposed in the literature.

Cette thèse a pour but d’étudier les activités humaines à travers l’analyse du flux de signalisation du réseau cellulaire de données (GTP). Pour ce faire, nous avons mis en place un ensemble d’outils nous permettant de collecter, stocker et analyser ces données de signalisation. Ceci en se basant sur une architecture indépendante au maximum des constructeurs de matériel. À partir des données extraites par cette plateforme nous avons fait trois contributions.Dans une première contribution, nous présentons l’architecture de la plateforme de capture et d’analyse de la signalisation GTP dans un réseau d’opérateur. Ce travail a pour but de faire l’inventaire des différents éléments déclenchant des mises à jour et aussi d’estimer la précision temporelle et spatiale des données collectées. Ensuite, nous présentons une série de mesures, mettant en avant les caractéristiques principales de la mobilité humaine observées au travers de la signalisation mobile (le temps inter-arrivées des messages de mise à jour, la distance observée des sauts entre cellules lors des déplacements des clients). Finalement, nous présentons l’analyse des compromis qui ont été faits entre la rapidité d’écriture/de lecture et la facilité d’usage du format de fichier utilisé lors de l’échange d’informations entre les sondes de capture et le système stockage. Deuxièmement, nous avons été capables de mettre en place un algorithme de reconstitution de trajets. Cet algorithme permet, à partir de données éparses issues du réseau cellulaire, de forger des trajets sur les voies de transport. Il se base sur les données des trajets sous-échantillonnées et en déduit les positions du client sur les voies de communication. Nous avons mis en place un graphe de transport intermodal. Celui-ci porte sur le métro, le train et le réseau routier. Il connecte les différents points entre eux dans chacune des couches de transport et interconnecte les modes de transport entre eux, aux intersections. Notre algorithme se base sur un modèle de chaîne de Markov cachée pour placer sur le graphe les positions probables des individus entre les différentes observations. L’apport de ce travail est l’utilisation des propriétés topologiques du réseau de transport afin de renseigner les probabilités d’émission et de transition dans un modèle non supervisé. Ces travaux ont donné lieu à une publication et à un brevet. Finalement, notre dernière contribution utilise les données issues de la signalisation à des fins de dimensionnement du réseau mobile d’opérateur. Il s’agit de dimensionner dynamiquement un réseau mobile en utilisant les bandes de fréquences dites vTV-Whitespace. Ces bandes de fréquences sont libérées sous certaines conditions aux USA et soumises à vente aux enchères. Ce que nous proposons est un système basé sur un algorithme de qualité d’expérience (QoE) et sur le coût de la ressource radio afin de choisir où déployer des femtocells supplémentaires et où en supprimer en fonction des variations de population par unité d’espace. En conclusion, cette thèse offre un aperçu du potentiel de l’analyse des metadata de signalisation d’un réseau dans un contexte plus général que la simple supervision d’un réseau d’opérateur / The aim of this thesis is to study human activities through the analysis of the signaling flow in cellular data network (GTP). In order to achieve this goal, we implemented a set of tools allowing us to collect, store and analyze this signaling data. We created an architecture independent at most of hardware manufacturers and network operators. Using data extracted by this platform we made three main contributions. In our first contribution, we present the GTP capture and analysis platform in a mobile operator network. This work intends to list the different elements triggering updates and to estimate the temporal and spatial accuracy of the data collected. Next, we present a set of measures that represent the main characteristics of human mobility observed through the mobile signaling data (the inter-arrival time of update messages, the observed distances of hops from cell to cell made by moving users). Finally, we present the analysis of the compromise that was made between the writing/reading performances and the ease of use of the file format for the data storage. In our second contribution, we propose CT-Mapper, an unsupervised algorithm that enables the mapping of mobile phone traces over a multimodal transport network. One of the main strengths of CT-Mapper is its capability to map noisy sparse cellular multimodal trajectories over a multilayer transportation network where the layers have different physical properties and not only to map trajectories associated with a single layer. Such a network is modeled by a large multilayer graph in which the nodes correspond to metro/train stations or road intersections and edges correspond to connections between them. The mapping problem is modeled by an unsupervised HMM where the observations correspond to sparse user mobile trajectories and the hidden states to the multilayer graph nodes. The HMM is unsupervised as the transition and emission probabilities are inferred using respectively the physical transportation properties and the information on the spatial coverage of antenna base stations. Finally, in our last contribution we propose a method for cellular resource planning taking into account user mobility. Since users move, the bandwidth resource should move accordingly. We design a score based method using TV Whitespace, and user experience, to determine from which cell resource should be removed and to which one it should be added. Combined with traffic history it calculates scores for each cell. Bandwidth is reallocated on a half-day basis. Before that, real traces of cellular networks in urban districts are presented which confirm that static network planning is no longer optimal. A dynamic femtocell architecture is then presented. It is based on mesh interconnected elements and designed to serve the score based bandwidth allocation algorithm. The score method along with the architecture are simulated and results are presented. They confirm the expected improvement in bandwidth and delay per user while maintaining a low operation cost at the operator side. In conclusion, this thesis provides an overview of the potential of analyzing the signaling metadata of a network in a broader context that supervision of an operator network