Aujourd'hui, l'extension des exigences du trafic de données sans fil dépasse le taux de croissance de la capacité des nouvelles technologies d'accès sans fil. Par conséquent, les réseaux sans fil mobiles de la future génération proposent des architectures hétérogènes, généralement appelées réseaux sans fil hétérogènes (HWN). HWN se caractérisent par l'intégration des réseaux cellulaires et des réseaux locaux sans fil (WLAN) pour répondre aux besoins des utilisateurs et améliorer la capacité du système. En fait, l'intégration de différents types de technologies d'accès sans fil dans HWN offre des choix flexibles pour que les utilisateurs soient associés au réseau qui répond le mieux à leurs besoins. Dans ce contexte, cette thèse traite le problème d'association d'utilisateurs et le problème d'allocation de ressources dans un système sans fil hétérogène basé sur des points d'accès Wi-Fi intégrés et des stations de base L TE. Les contributions de cette thèse pourraient être divisées en trois parties principales. Dans la première partie, un nouveau problème d'association d'utilisateurs et d'optimisation de l'allocation des ressources est formulé pour maximiser la satisfaction globale des utilisateurs dans le système. La satisfaction de l'utilisateur est basée sur une fonction de profit pondérée qui vise à améliorer la puissance relative du signal reçu et la diminution de la consommation d'énergie des terminaux mobiles (MT). Étant donné qu'un MT n'est autorisé à être associé qu'à un seul réseau à la fois, le problème d'optimisation formulé est binaire avec une complexité NP complète. Ensuite, plusieurs solutions centralisées avec une complexité à temps polynomial sont proposées pour résoudre le problème formulé. Les solutions proposées sont basées sur des approches heuristiques et sur la relaxation continue du problème d'optimisation binaire formulé. La deuxième partie de la thèse vise à fournir une solution distribuée pour le problème formulé. La solution distribuée proposée déploie la technique de détente lagrangienne pour convertir le problème global formulé en plusieurs problèmes de Knapsack distribués, chaque réseau traite son problème Knapsack correspondant. La méthode de sous gradient est utilisée pour trouver les multiplicateurs lagrangiens optimaux ou sous optimaux. Enfin, la troisième partie de la thèse étudie de nouvelles perspectives de la formulation du problème d'optimisation et ses solutions centralisées et distribuées correspondantes. Un problème d'association d'utilisateurs et d'allocation de ressources basé sur la priorité est formulé. Le problème est ensuite réduit en plusieurs problèmes résolus à l'aide des solutions proposées réparties et centralisées. En outre, une nouvelle solution de maximisation de l'efficacité énergétique est proposée en modifiant les objectifs du problème d'optimisation originalement formulé. / It is indicated that the expansion of the wireless data traffic requirements exceeds the capacity growth rate of new wireless access technologies. Therefore, next-generation mobile wireless networks are moving toward heterogeneous architectures usually referred to as heterogeneous wireless networks (HWNs). HWNs are usually characterized by the integration of cellular networks and wireless local area networks (WLANs) to meet user requirements and enhance system capacity. In fact, integrating different types of wireless access technologies in HWNs provides flexible choices for users to be associated with the network that best satisfies their needs. In this context, this thesis discusses the user association and downlink resource allocation problem in a heterogeneous wireless system that is based on integrated Wi-Fi access points (APs) and long-term evolution (L TE) base stations (BSs). The contributions of this thesis could be divided into three main parts. In the first part, a novel user association and resource allocation optimization problem is formulated to maximize the overall user satisfaction in the system. The user satisfaction is based on a weighted profit function that aims at enhancing the relative received signal strength and decreasing the power consumption of mobile terminals (MTs). Since a MT is only allowed to be associated with a single network at a time, the formulated optimization problem is binary with an NP-complete complexity. Then, multiple centralized solutions with polynomial-time complexities are proposed to solve the formulated problem. The proposed centralized solutions are based on heuristic approaches and on the continuous re laxation of the formulated binary optimization problem. The second part of the thesis aims at providing a distributed solution for the formulated problem. The proposed distributed solution deploys the Lagrangian relaxation .technique in order to convert the global formulated problem into multiple distributed Knapsack problems each network processes its corresponding Knapsack problem. The sub-gradient method is used in order to find the optimal, or near optimal, Lagrangian multipliers. Finally, the third part of the thesis studies new perspectives of the formulated optimization problem and its corresponding centralized and distributed solutions. Mainly, a generalized priority-aware user association and resource allocation problem is formulated. The priority-aware problem is then reduced into multiple problems that are solved using the proposed centralized and distributed solutions. Moreover, a novel power efficiency maximization solution is proposed by altering the objectives of the main formulated optimization problem.

Les grilles de calcul et le “cloud computing” permettent de distribuer un ensemble de ressources informatiques, telles que du stockage ou du temps de calcul, à un ensemble d’utilisateurs en fonction de leurs demandes en donnant l’illusion de ressources infinies. Cependant, lorsque l’ensemble de ces ressources est insuffisant pour satisfaire les exigences des utilisateurs, des conflits d’intérêts surgissent. Ainsi, un libre accès à des ressources limitées peut entraîner une utilisation inefficace qui pénalise l’ensemble des participants. Dans de tels environnements, il devient nécessaire d’établir des procédures d’arbitrage afin de résoudre ces conflits en garantissant une distribution équitable aux différents utilisateurs. Nous présentons une nouvelle classe de problèmes : celle des ordonnancements multi-utilisateurs. Cette thèse aborde la notion d’équité au travers de problèmes d’allocation de ressources sous incertitudes et d’ordonnancement de tâches périodiques. / Grid and Cloud computing make possible the sharing of computer system resources, such as storage or computation time, among a set of users, according to their requests, thereby creating an illusion of infinite resources. However, as soon as those resources are insufficient to meet users’s expectations, conflicts of interest arise. Therefore, unlimited access to limited resources may lead to inefficient usage which penalizes the whole set of users. In such environments, arbitration becomes necessary in order to settle those conflicts and ensure a fair allocation to all users. We present two classes of problems : multi-user resource allocation under uncertainty and multi-user periodic task scheduling. We tackle these problems from the point of view of fairness.

La plupart des infrastructures de cloud efficace en énergie proposées dans la littérature ne tiennent pas compte de la disponibilité électrique et des énergies renouvelables dans leurs modèles. L’intégration des énergies renouvelables dans les centres de données réduit considérablement leur consommation d’énergie et leur empreinte carbone. Étant donné que l’énergie renouvelable est intermittente et fluctue en fonction du temps, elle est habituellement sous-utilisée. Nous abordons le problème de l’amélioration de l’utilisation des énergies renouvelables dans un centre de données unique et étudions deux approches : la planification opportuniste et le stockage de l’énergie. Nos résultats démontrent que les deux approches permettent de réduire la consommation d’énergie non-renouvelable sous différentes configurations. Nous étendons ce travail au contexte des Edge Clouds et de l’Internet des Objets dans le cas de l’analyse de flux de données. Nous montrons comment rendre les Edge Clouds plus verts avec une production d’énergie renouvelable sur site combinée à un stockage d’énergie et à une dégradation de performance des applications des utilisateurs. / Most of the energy-efficient Cloud frameworks proposed in literature do not consider electricity availability and renewable energy in their models. Integrating renewable energy into data centers significantly reduces the traditional energy consumption and carbon footprint of these energy-hungry infrastructures. As renewable energy is intermittent and fluctuates with time-varying, it is usually under-utilized. We address the problem of improving the utilization of renewable energy for a single data center and investigate two approaches: opportunistic scheduling and energy storage. Our results demonstrate that both approaches are able to reduce the brown energy consumption under different configurations. We extend this work to the context of Edge Clouds and Internet of Things on the use case of data stream analysis. We show how to make Edge Clouds greener with on-site renewable energy production combined with energy storage and performance degradation of the users’ applications.

Les réseaux de transport optiques constituent aujourd'hui l'infrastructure de base des systèmes de communications modernes. Etant donné les investissements colossaux nécessaires au déploiement de ces réseaux, liés en particulier aux coûts des équipements (fibres optiques, cartes, transpondeurs,...), l'optimisation du routage et de l'allocation de ressources est indispensable pour maitriser les coûts d'exploitation. Dans ce contexte, ces travaux de thèse étudient un ensemble de problèmes d'allocation de ressources qui se posent lors de la planification des réseaux SDH (Synchronous Digital Hierarchy) et WDM (Wavelength Division Multiplexing), mais aussi lors de celle des réseaux multicouches basés sur une couche de transport optique. Dans un premier temps, nous étudions le problème du routage des circuits dans les réseaux SDH avec pour objectif principal de minimiser la fragmentation de la bande passante. Nous formulons ce problème comme un programme linéaire en nombres entiers intégrant un ensemble de contraintes réalistes de routage, de transmission et de brassage et utilisant des coûts de ressources granulaires. Un algorithme exact et deux heuristiques sont proposés pour résoudre ce problème. Nous abordons également le problème du reroutage des circuits SDH qui se pose aux opérateurs lorsqu'il devient indispensable de réduire la fragmentation de la bande passante. Nous montrons sur des instances réelles des problèmes étudiés que les méthodes proposées permettent des gains économiques considérables. Dans un deuxième temps, nous étudions deux problèmes de planification pour l'optimisation des réseaux WDM. Le premier problème est celui du design de la topologie logique, c'est à dire celui de la définition des circuits (chemins) optiques permettant de router un ensemble de demandes en trafic avec un coût de transpondeurs minimal. Le second problème est celui du routage et de l'affectation de longueurs d'onde: comment router les circuits optiques définis précédemment pour minimiser le nombre de longueurs d'onde utilisées tout en respectant un ensemble de contraintes technologiques? Nous formulons ces deux problèmes comme des programmes linéaires en nombres entiers et proposons des heuristiques efficaces, de type approximation successive pour le premier problème et utilisant une approche par décomposition pour le second problème. Là encore, les résultats expérimentaux montrent que les méthodes proposées permettent d'obtenir des approximations de qualité pour des instances de très grandes tailles. Enfin, nous abordons l'allocation de ressources dans les réseaux multicouches de nouvelle génération IP/MPLS sur OTN (Optical Transport Network) sur DWDM (Dense WDM). Dans ce cas, la question à laquelle la majorité des opérateurs cherchent une réponse est celle du routage des demandes en trafic de niveau 3 permettant d'optimiser l'allocation des ressources non seulement dans la couche IP/MPLS mais aussi dans les couches sous-jacentes OTN et DWDM. Pour répondre à cette question, nous proposons un nouveau modèle d'optimisation multicouche qui tient compte d'une hiérarchie de contraintes matérielles et définit un compromis entre les coûts des ressources dans les trois couches de réseau. L'ensemble des algorithmes d'optimisation proposés ont été intégrés dans l'environnement de planification et d'optimisation de réseaux NEST de la société QoS Design, utilisé par de grands opérateurs pour planifier leurs réseaux. / Optical transport networks currently constitute base infrastructures for modern day telecommunications systems. Given the huge investments required for deploying these networks, and in particular concerning equipment costs (fiber optics, cards, transponders, etc.), routing optimization and resource allocation are indispensable issues for mastering the operational expenditures (OPEX). In this context, the work conducted in this thesis handle a set of resource allocation problems which arise while planning not only optical SDH (Synchronous Digital Hierarchy) and WDM (Wavelength Division Multiplexing) networks, but also multilayer ones based on an optical transport layer. First, the circuit routing problem in SDH networks is tackled with the main objective of minimizing the bandwidth fragmentation. This problem is formulated as an Integer Linear Program (ILP) integrating a set of realistic routing, transmission and cross-connect constraints and using granular resource costs. An exact algorithm and two heuristics are proposed to solve this problem. The rerouting problem of SDH circuits, which faces operators when it becomes absolutely necessary to reduce the bandwidth fragmentation in the network, is also addressed. For real instances of the studied problems, it is shown that the proposed methods provide considerable economic gains. Second, two planning problems for WDM network optimization is tackled. The first problem is that of the logical network design, or in other words that concerned with the definition of lightpaths to route a set of traffic demands with a minimum transponder cost. The second problem is related to the routing and the wavelength assignment: how to route the previously defined lightpaths so as to minimize the total number of assigned wavelengths while respecting a set of technological constraints? These two problems are formulated as Integer Linear Programs (ILPs) and are solved using efficient heuristics, based on a successive approximation for the first problem and a decomposition approach for the second one. Here again, experimental results show that the proposed methods allow obtaining good quality approximations for large scale instances. Finally, resource allocation in new generation multilayer networks, that is IP/MPLS over OTN (Optical Transport Network) over DWDM (Dense WDM), is addressed. In this case, the question that most of the operators seek to answer is how to route layer 3 traffic demands while optimizing resource allocation, not only in the IP/MPLS layer, but also in the underlying OTN and DWDM layers. For this purpose, a new multilayer optimization model is proposed. It takes into account a hierarchy of material constraints and defines a tradeoff between the resource costs in the three network layers. The set of proposed optimization algorithms have been integrated into the network planning and optimization environment NEST of QoS Design, which is used by major operators to plan their network.

Cloud-Radio Access Network (C-RAN) est une architecture prometteuse pour faire face à l’augmentation exponentielle des demandes de trafic de données et surmonter les défis des réseaux de prochaine génération (5G). Le principe de base de CRAN consiste à diviser la station de base traditionnelle en deux entités : les unités de bande de base (BaseBand Unit, BBU) et les têtes radio distantes (Remote Radio Head, RRH) et à mettre en commun les BBUs de plusieurs stations dans des centres de données centralisés (pools de BBU). Ceci permet la réduction des coûts d’exploitation, l’amélioration de la capacité du réseau ainsi que des gains en termes d’utilisation des ressources. Pour atteindre ces objectifs, les opérateurs réseaux ont besoin d’investiguer de nouveaux algorithmes pour les problèmes d’allocation de ressources permettant ainsi de faciliter le déploiement de l’architecture C-RAN. La plupart de ces problèmes sont très complexes et donc très difficiles à résoudre. Par conséquent, nous utilisons l’optimisation combinatoire qui propose des outils puissants pour adresser ce type des problèmes.Un des principaux enjeux pour permettre le déploiement du C-RAN est de déterminer une affectation optimale des RRHs (antennes) aux centres de données centralisés (BBUs) en optimisant conjointement la latence sur le réseau de transmission fronthaul et la consommation des ressources. Nous modélisons ce problème à l’aide d’une formulation mathématique basée sur une approche de programmation linéaire en nombres entiers permettant de déterminer les stratégies optimales pour le problème d’affectation des ressources entre RRH-BBU et nous proposons également des heuristiques afin de pallier la difficulté au sens de la complexité algorithmique quand des instances larges du problème sont traitées, permettant ainsi le passage à l’échelle. Une affectation optimale des antennes aux BBUs réduit la latence de communication attendue et offre des gains en termes d’utilisation des ressources. Néanmoins, ces gains dépendent fortement de l’augmentation des niveaux d’interférence inter-cellulaire causés par la densité élevée des antennes déployées dans les réseaux C-RANs. Ainsi, nous proposons une formulation mathématique exacte basée sur les méthodes Branch-and-Cut qui consiste à consolider et ré-optimiser les rayons de couverture des antennes afin de minimiser les interférences inter-cellulaires et de garantir une couverture maximale du réseau conjointement. En plus de l’augmentation des niveaux d’interférence, la densité élevée des cellules dans le réseau CRAN augmente le nombre des fonctions BBUs ainsi que le trafic de données entre les antennes et les centres de données centralisés avec de fortes exigences en termes de latence sur le réseau fronthaul. Par conséquent, nous discutons dans la troisième partie de cette thèse comment placer d’une manière optimale les fonctions BBUs en considérant la solution split du 3GPP afin de trouver le meilleur compromis entre les avantages de la centralisation dans C-RAN et les forts besoins en latence et bande passante sur le réseau fronthaul. Nous proposons des algorithmes (exacts et heuristiques) issus de l’optimisation combinatoire afin de trouver rapidement des solutions optimales ou proches de l’optimum, même pour des instances larges du problèmes. / Cloud Radio Access Network (C-RAN) has been proposed as a promising architecture to meet the exponential growth in data traffic demands and to overcome the challenges of next generation mobile networks (5G). The main concept of C-RAN is to decouple the BaseBand Units (BBU) and the Remote Radio Heads (RRH), and place the BBUs in common edge data centers (BBU pools) for centralized processing. This gives a number of benefits in terms of cost savings, network capacity improvement and resource utilization gains. However, network operators need to investigate scalable and cost-efficient algorithms for resource allocation problems to enable and facilitate the deployment of C-RAN architecture. Most of these problems are very complex and thus very hard to solve. Hence, we use combinatorial optimization which provides powerful tools to efficiently address these problems.One of the key issues in the deployment of C-RAN is finding the optimal assignment of RRHs (or antennas) to edge data centers (BBUs) when jointly optimizing the fronthaul latency and resource consumption. We model this problem by a mathematical formulation based on an Integer Linear Programming (ILP) approach to provide the optimal strategies for the RRH-BBU assignment problem and we propose also low-complexity heuristic algorithms to rapidly reach good solutions for large problem instances. The optimal RRH-BBU assignment reduces the expected latency and offers resource utilization gains. Such gains can only be achieved when reducing the inter-cell interference caused by the dense deployment of cell sites. We propose an exact mathematical formulation based on Branch-and-Cut methods that enables to consolidate and re-optimize the antennas radii in order to jointly minimize inter-cell interference and guarantee a full network coverage in C-RAN. In addition to the increase of inter-cell interference, the high density of cells in C-RAN increases the amount of baseband processing as well as the amount of data traffic demands between antennas and centralized data centers when strong latency requirements on fronthaul network should be met. Therefore, we discuss in the third part of this thesis how to determine the optimal placement of BBU functions when considering 3GPP split option to find optimal tradeoffs between benefits of centralization in C-RAN and transport requirements. We propose exact and heuristic algorithms based on combinatorial optimization techniques to rapidly provide optimal or near-optimal solutions even for large network sizes.

Cette thèse examine la façon dont les choix stratégique des firmes multi-établissements affectent la performance de leurs filiales et contribuent aux débats récurrents liés à la pertinence et l’importance de la stratégie d’entreprise. Dans le premier chapitre, nous nous intéressons à savoir le poids relatif des décisions stratégiques des sièges sociaux sur la performance de leurs établissements. Nous montrons l’incapacité des méthodes traditionnelles à rendre compte efficacement des effets entreprises. Nous soutenons en effet que les études précédentes sous-estiment systématiquement les effets entreprises car elles ne tiennent pas compte de l’hétérogénéité de l’impact des décisions des sièges sociaux sur leurs filiales. Une filiale peut recevoir une part très différente des ressources de l’entreprise. Par conséquent, le fait d’étudier toutes les filiales comme s’il s’agissait d’un seul groupe sous-estime systématiquement les effets entrepris. Nous soutenons plutôt qu’il est important de tenir compte de la variance induite par l’entreprise sur la performance des filiales. Nous appelons cette variance induite « effet entreprise variant », et montrons qu’elle est tout aussi importante que la valeur des effets entreprise standards, à savoir « les effets entreprise invariants ». Dans le deuxième chapitre nous nous sommes intéressés au débat relatif à l’efficacité des marchés de capitaux internes, comme une des sources essentielles d’hétérogénéité de la performance des filiales. La question centrale du débat consiste à discuter les modalités d’allocation optimale du capital. Les études empiriques mettent en évidence des montants d’allocation très au-dessus des niveaux optimaux dans des filiales qui ont des niveaux de croissance apparemment relativement faibles. Tenant compte à la fois du degré d’incertitude auquel une firme est confrontée lorsqu’elle décide d’allouer son capital et du niveau d’interdépendance de ses filiales, nous distinguons « les déviations inefficaces » des « déviations non nécessairement inefficaces ». Nous expliquons que les déviations par rapport à la logique de sélection des gagnants dans les décisions d’allocation de capital peuvent simplement refléter des intentions stratégiques différentes plutôt que des inefficacités d’allocation. De plus, nous soulignons le rôle de l’ampleur de l’expérience antérieure des dirigeants dans le domaine des filiales, en tant que source de compétences en allocation de capital des firmes, dans l’atténuation des déviations inefficaces et l’augmentation de la valeur de la corporation grâce à de meilleures pratiques d’allocation du capital. Le troisième chapitre incorpore les ressources financières à la théorie de redéploiement des ressources. La théorie standard a exclu les ressources financières qui, par définition, peut être allouée et ré-allouées à tout type d’investissement sans contrainte. Nous soutenons toutefois que, lors de l’affectation vers l’une de ses filiales de ressources financières à des investissements imparfaitement fongibles ou divisibles, telles que le capital physique, tel que des usines ou des technologies, le siège social achète également l’option de redéploiement de ces mêmes ressources dans le futur. En effet, le choix d’investissement présent doit être réalisé en tenant compte des coûts de redéploiement éventuels dans le futur. Par conséquent, la direction des flux de capitaux actuels entre les filiales ne sera pas simplement réalisée en fonction des opportunités actuelles de croissance relative du marché, mais aussi en fonction des coûts d’ajustement due aux redéploiements éventuels entre les filiales dans les périodes ultérieures. Cette extension permet d’étendre le champ d’études empiriques de la théorie du redéploiement de ressources non-financier. En effet, les études empiriques dans ce domaine ont été rares jusqu'à présent en raison du défi que représentent l'observation et la mesure du redéploiement des ressources non financières. / This dissertation deals with how multi-business firms’ strategies affect the performance of subsidiary businesses and contributes to long standing debates in corporate strategy. Overall, each of my 3 dissertation essays are designed to, correspondingly, analyze the debated magnitude, efficiency, and mechanism of the effect of a multi-business firms’ strategies on the performance of its subsidiaries. In the first chapter, I address a root question in corporate level strategy; I question traditional methods to estimate corporate effects (the effect of corporate headquarters on subsidiary businesses’ performance). I argue that previous corporate effect studies fail to account for the uneven impact of corporate decisions on subsidiaries. A headquarters makes conscious and deliberate decisions that might induce performance heterogeneity among its subsidiaries. Consequently, considering all subsidiaries as a bundle will systematically underestimate the corporate effects. Rather, I argue that it is important to account for the firm’s induced variance on the subsidiaries’ performance. We connote this induced variance as “business-variant corporate effects”, and show that they are just as important in magnitude as the value of the standard corporate effects, namely “business-invariant corporate effects”, found in previous studies. In the second essay, I focus on corporate capital allocation as a critical dimension of corporate strategies that might contribute to, within-firm, subsidiaries’ performance heterogeneity. We particularly delve deeper into the internal capital market efficiency debate by extending current theories that aim to justify why headquarters provide more resources to subsidiaries with seemingly lower growth opportunities. Considering both the level of uncertainty a firm faces when making capital allocation decisions, and the level of interdependence among its subsidiaries, we disentangle between inefficient and not-necessarily-inefficient deviations from standard models’ prescription. We explain that higher investments in subsidiaries with seemingly lower growth opportunities may simply reflect different strategic intents rather than allocation inefficiencies. Furthermore, we highlight the role of the breadth of CEOs’ prior experience in subsidiaries’ domain, as a source of firms’ capital allocation competency, in attenuating inefficient deviations and enhancing corporate value through better capital allocation practices. In the third essay, I incorporate financial resources, as a perfectly fungible and divisible resource, within the scope of the resource redeployment theory. Indivisibility and imperfect fungibility of resources play a critical role in the theory and this is why the standard theory has excluded the financial resources from its boundaries. I, however, argue that when allocating financial resources, such as capital, to one of its subsidiaries to acquire non-financial assets such as plants or technology, a corporate headquarters also purchases the option to redeploy those same resources in subsequent periods. Therefore, the direction of current capital flow among subsidiary businesses will not merely be a function of their current relative market growth opportunities. Rather, it is a function of the adjustment costs of potential resource redeployments among the subsidiaries in subsequent periods. My extension of the resource redeployment theory to include intrafirm capital allocations paves the way for further empirical investigations of the theory; that have been scarce so far, due to the challenge of observing and measuring the redeployment of non-financial resources. In turn, studying intrafirm capital allocations through the lens of RR theory helps us further develop and offer novel predictions for the theory.

Dans cette thèse, nous étudions le problème de l'allocation de ressources dans le cadre des réseaux 4G LTE. La méthode d'accès OFDMA qui est utilisée partage les ressources radios à la fois dans le domaine fréquentiel et temporel. En raison des déficiences du canal, les utilisateurs ne bénéficient pas toujours des mêmes débits d'émission/réception sur chacune des ressources. Dans ce cadre, notre problème consiste à distribuer ces ressources radios aux mobiles afin de leur permettre de transmettre/recevoir des données. L'algorithme utilisé pour allouer les ressources a une importance fondamentale sur les performances du système. La norme LTE ajoute des contraintes supplémentaires à ce problème et rend l'exploitation de la diversité fréquentielle et de la diversité multi-utilisateurs plus difficile. En effet, sous ces contraintes, nous montrons que le problème de l'allocation de ressources fait alors partie de la classe des problèmes « difficiles ». Par conséquent, les algorithmes classiques de la littérature sont souvent inadaptés à un réseau LTE réel. Nous proposons des algorithmes d'allocation de ressources à la fois pour le sens montant et descendant de LTE. Les contraintes de la norme sont rigoureusement prises en compte afin de construire des solutions efficaces. De plus, les algorithmes proposés sont génériques et peuvent donc s'adapter à une grande variété d'objectifs. En particulier, nous nous attachons à prendre en charge les trafics multimédias dont les débits et les besoins en qualité de service sont très hétérogènes (taux d’erreurs binaires, retard, gigue, etc.). En effet, l'augmentation progressive des débits et la forte popularité des équipements mobiles intelligents amènent à une utilisation toujours plus massive des applications multimédias. Tous nos algorithmes sont validés par simulation. Par ce biais, nous montrons que la prise en compte des contraintes de LTE est essentielle à l'obtention de performances élevées. / In this thesis, we study the resource allocation problem within the framework of 4G LTE networks. The OFDMA access method divides the radio resources both in the frequency and time domains. Due to channel impairments, users do not always have the same transmit/receive rates on each resource. In this context, our problem is to share the radio resources between users and enable them to transmit/receive data. The algorithm used to allocate resources is of fundamental importance on system performance. The LTE standard adds constraints to this problem and makes harder the exploitation of the frequency and the multi-user diversity. Indeed, under these constraints, we show that the resource allocation problem becomes part of the « most difficult » problems. Therefore, the conventional algorithms are often not adapted to a real LTE network. We provide resource allocation algorithms for both the uplink and downlink of LTE. The constraints of the standard are rigorously taken into account in order to build effective solutions. In addition, the proposed algorithms are generic and can adapt to a wide variety of objectives. In particular, we focus on the support of multimedia traffic with heterogeneous quality of service requirements (bit error rate, delay, jitter, etc.). Indeed, the gradual increase of the offered throughput and the strong popularity of smart mobile devices lead to a massive use of multimedia applications. Our algorithms are validated through extensive simulation. By this means, we show that the inclusion of LTE constraints is essential to achieving high performance.

La croissance rapide des applications interactives et ses demandes en termes de bande passante et de (QoS), a motivé le déploiement de la technologie optique aux réseaux métropolitains. Beaucoup de dispositifs optiques intelligents sont créés pour gérer efficacement la capacité énorme du réseau. L'explosion de la bande passante est principalement attribuable à la croissance du trafic de données dont la nature devient de plus en plus complexe. Actuellement, la plupart des trafics de données sont transportés dans les réseaux qui sont dominées par la technologie de commutation de circuit optique. Néanmoins, cette technique a quelques inconvénients tels que les propriétés inflexibles. Technologie de commutation de paquets optiques (OPS), qui offre des gains significatifs en termes de capacité de passage à l’échelle et d'efficacité de gestion des ressources du réseau, peut surmonter ces limitations. Cela a motivé l'orientation de la commutation de circuit optique à la commutation de paquet optique dans l’infrastructure future du réseau. En réalité, un réseau en anneau à commutation de paquet optique ( OPSR), qui combinent la flexibilité et la mise à l’échelle de la technologie de commutation de paquet avec les avantages de la topologie en anneau tels que la restitution rapide du service en cas de panne et un bon gain de multiplexage statistique du trafic, promettraient une bonne solution pour les réseaux MAN du future. Une nouvelle architecture du réseau OPSR qui se base sur l’infrastructure tout optique a proposé par des équipes de recherche chez Alcatel-Lucent. La nouvelle architecture offre des fonctions intelligentes, avec un coût moins élevé en optimisant le temps de traitement. Elle est envisagée de remplacer les architectures optoélectroniques existantes tels que Resilient Packet Ring. L'élément fondamental du réseau est Packet Optical Add/Drop Multiplexer (POADM) qui est implémenté à l'intérieur des nœuds d’accès, permettant aux nœuds d'exploiter la transparence optique. Cette thèse se concentre donc sur l'évaluation des performances de la nouvelle génération des réseaux optiques métropolitains. Dans cette thèse, nous avons analysé des performances (en termes de délais d’accès et de la distribution du taux de l’occupation au tampon local des nœuds d'accès) d'un bus optique synchrone qui soutient des paquets à taille fixe. Nous avons modélisé chaque nœud d'accès par une chaîne de Markov à temps discret (EDTMC). La solution de l'EDTMC nous permet de calculer la probabilité approximative où les nœuds d'accès dans le bus peuvent "voir" slots libres dans la ligne de transit. En utilisant une technique d'analyse récursive, nous déduisons une formule mesurant le temps moyen d'attente des paquets du client venant de la couche supérieure, ainsi que la distribution du taux de l’occupation au tampon local des nœuds d'accès pour les deux cas: avec et sans garantie QoS). Pour caractériser des performances d'un réseau OPSR asynchrone, nous avons évalué l'impact de la création de containeur optique à taille fixe sur les performances du réseau. L’analyse des performances de ce système nous a permis d'identifier une combinaison raisonnable de certains paramètres (la durée de timeslot, les valeurs d’expiration des temporisateurs, le profil du trafic client, la charge du réseau) qui peuvent améliorer l'utilisation de la bande passante du réseau. Le point le plus important que nous avons mentionné dans la thèse est la comparaison entre deux approches architecturales: le modèle de Variable Length - Optical Packet Format (VL-OPF) versus le modèle de Fixed Length - Optical Packet Format (FL-OPF). En plus de Cos-Upgrade Mécanisme (CUM) qui est proposé d'améliorer le taux de remplissage du conteneur optique, nous avons proposé un nouveau mécanisme appelé Dynamic Upgrade Cos-Mécanisme (DCUM), où les valeurs des temporisateurs sont modifiés dynamiquement en fonction de l'état des tampons locaux aux nœuds d’accès et le trafic circulant dans le réseau / The rapid growth in client application demands, in terms of bandwidth and (QoS), has motivated the deployment of the optical technology at Metro Access and Metro Core Networks. More diverse and more intelligent optic devices are required for efficiently management of huge capacity in the network. The explosion in demand for network bandwidth is mainly due to the growth in data traffic whose nature is also becoming more and more complex. In general, most of service-based traffics are transported in networks which are now being dominated by the optical switching technology. Nevertheless, such technology has some drawbacks such as inflexible and non-scalable properties. (OPS), which offers significant benefits in terms of both network efficiency and control scalability, may overcome these limitations. This has motivated the orientation from optical circuit switching to optical packet switching in the future network infrastructure. In reality, optical packet switching ring (OPSR) networks, which combine the packet switching technology with the well-known advantages of ring topology such as fast service restoration in cases of failure and high gain of statistical traffic multiplexing over the ring, appear to be the technology of choice for the next generation of Metro Area Networks. A new OPSR architecture which is based on the all-optical infrastructure that offers intelligent features with lower cost while maximizing processing time and is now considering being replaced existing opto-electronic architectures such as Resilient Packet Ring, have been presented in the scope of the dissertation. The key element of such network is Packet Optical Add/Drop Multiplexer (POADM) which is implemented inside a ring node, allowing the node to exploit the optical transparency. This dissertation hence focuses on the performance evaluation of the new generation of OPSR network. In this dissertation, we have investigated the performance analysis (in terms of packet delay and queue-length distribution of access nodes) of an optical synchronous bus-based metropolitan network supporting fixed-size packets. We have modeled each access node by an embedded discrete time Markov chain (EDTMC). The solution of the EDTMC allows us to compute the approximate probability that access nodes on the bus “see” free slots in the transit line. Using a recursive analysis technique, we approximately outline the mean waiting time of client packets coming from the upper layer as well as an approximate queue-length distribution of local buffers at access nodes in two cases: with and without QoS guarantees. To characterize the performance of an asynchronous OPSR network, we have evaluated the impact of Optical fixed-Size Packet Creation on the network performance without and with different quality of services (QoS) requirements. Performance analysis of such systems has allowed us to identify a reasonable combination of some parameters (timeslot duration, timer expiration values, profile of client traffic and network load) which may be able to improve the bandwidth utilization of the network for a given traffic matrix. The most important point that we have mentioned in the dissertation is the comparison of two architectural approaches: Variable Length – Optical Packet Format (VL-OPF) model supporting empty packets versus Fixed Length – Optical Packet Format (FL-OPF) model. In addition to CoS-Upgrade Mechanism (CUM) which is proposed to improve the filling ratio of the optical container, we have proposed a novel mechanism named Dynamic CoS-Upgrade Mechanism (DCUM) where timers are dynamically changed according to the state of the local buffer of network nodes and the traffic circulating in the network, in order to create containers with a high filling ratio while limiting the time needed for their creation.

L'informatique en nuage (Cloud Computing) a émergé comme un nouveau paradigme pour offrir des ressources informatiques à la demande et pour externaliser des infrastructures logicielles et matérielles. Le Cloud Computing est rapidement et fondamentalement en train de révolutionner la façon dont les services informatiques sont mis à disposition et gérés. Ces services peuvent être demandés à partir d'un ou plusieurs fournisseurs de Cloud d'où le besoin de la mise en réseau entre les composants des services informatiques distribués dans des emplacements géographiquement répartis. Les utilisateurs du Cloud veulent aussi déployer et instancier facilement leurs ressources entre les différentes plateformes hétérogènes de Cloud Computing. Les fournisseurs de Cloud assurent la mise à disposition des ressources de calcul sous forme des machines virtuelles à leurs utilisateurs. Par contre, ces clients veulent aussi la mise en réseau entre leurs ressources virtuelles. En plus, ils veulent non seulement contrôler et gérer leurs applications, mais aussi contrôler la connectivité réseau et déployer des fonctions et des services de réseaux complexes dans leurs infrastructures virtuelles dédiées. Les besoins des utilisateurs avaient évolué au-delà d'avoir une simple machine virtuelle à l'acquisition de ressources et de services virtuels complexes, flexibles, élastiques et intelligents. L'objectif de cette thèse est de permettre le placement et l'instanciation des ressources complexes dans des infrastructures de Cloud distribués tout en permettant aux utilisateurs le contrôle et la gestion de leurs ressources. En plus, notre objectif est d'assurer la convergence entre les services de cloud et de réseau. Pour atteindre ces objectifs, cette thèse propose des algorithmes de mapping d'infrastructures virtuelles dans les centres de données et dans le réseau tout en respectant les exigences des utilisateurs. Avec l'apparition du Cloud Computing, les réseaux traditionnels sont étendus et renforcés avec des réseaux logiciels reposant sur la virtualisation des ressources et des fonctions réseaux. En plus, le nouveau paradigme d'architecture réseau (SDN : Software Defined Networks) est particulièrement pertinent car il vise à offrir la programmation du réseau et à découpler, dans un équipement réseau, la partie plan de données de la partie plan de contrôle. Dans ce contexte, la première partie de la thèse propose des algorithmes optimaux (exacts) et heuristiques de placement pour trouver le meilleur mapping entre les demandes des utilisateurs et les infrastructures sous-jacentes, tout en respectant les exigences exprimées dans les demandes. Cela inclut des contraintes de localisation permettant de placer une partie des ressources virtuelles dans le même nœud physique. Ces contraintes assurent aussi le placement des ressources dans des nœuds distincts. Les algorithmes proposés assurent le placement simultané des nœuds et des liens virtuels sur l'infrastructure physique. Nous avons proposé aussi un algorithme heuristique afin d'accélérer le temps de résolution et de réduire la complexité du problème. L'approche proposée se base sur la technique de décomposition des graphes et la technique de couplage des graphes bipartis. Dans la troisième partie de la thèse, nous proposons un cadriciel open source (framework) permettant d'assurer la mise en réseau dynamique entre des ressources Cloud distribués et l'instanciation des fonctions réseau dans l'infrastructure virtuelle de l'utilisateur. Ce cadriciel permettra de déployer et d'activer les composants réseaux afin de mettre en place les demandes des utilisateurs. Cette solution se base sur un gestionnaire des ressources réseaux "Cloud Network Gateway Manager" et des passerelles logicielles permettant d'établir la connectivité dynamique et à la demande entre des ressources cloud et réseau [...] / Cloud computing has rapidly emerged as a successful paradigm for providing IT infrastructure, resources and services on a pay-per-use basis over the past few years. As, the wider adoption of Cloud and virtualization technologies has led to the establishment of large scale data centers that consume excessive energy and have significant carbon footprints, energy efficiency is becoming increasingly important for data centers and Cloud. Today data centers energy consumption represents 3 percent of all global electricity production and is estimated to further rise in the future. This thesis presents new models and algorithms for energy efficient resource allocation in Cloud data centers. The first goal of this work is to propose, develop and evaluate optimization algorithms of resource allocation for traditional Infrastructutre as a Service (IaaS) architectures. The approach is Virtual Machine (VM) based and enables on-demand and dynamic resource scheduling while reducing power consumption of the data center. This initial objective is extended to deal with the new trends in Cloud services through a new model and optimization algorithms of energy efficient resource allocation for hybrid IaaS-PaaS Cloud providers. The solution is generic enough to support different type of virtualization technologies, enables both on-demand and advanced resource provisioning to deal with dynamic resource scheduling and fill the gap between IaaS and PaaS services and create a single continuum of services for Cloud users. Consequently, in the thesis, we first present a survey of the state of the art on energy efficient resource allocation in cloud environments. Next, we propose a bin packing based approach for energy efficient resource allocation for classical IaaS. We formulate the problem of energy efficient resource allocation as a bin-packing model and propose an exact energy aware algorithm based on integer linear program (ILP) for initial resource allocation. To deal with dynamic resource consolidation, an exact ILP algorithm for dynamic VM reallocation is also proposed. This algorithm is based on VM migration and aims at constantly optimizing energy efficiency at service departures. A heuristic method based on the best-fit algorithm has also been adapted to the problem. Finally, we present a graph-coloring based approach for energy efficient resource allocation in the hybrid IaaS-PaaS providers context. This approach relies on a new graph coloring based model that supports both VM and container virtualization and provides on-demand as well as advanced resource reservation. We propose and develop an exact Pre-coloring algorithm for initial/static resource allocation while maximizing energy efficiency. A heuristic Pre-coloring algorithm for initial resource allocation is also proposed to scale with problem size. To adapt reservations over time and improve further energy efficiency, we introduce two heuristic Re-coloring algorithms for dynamic resource reallocation. Our solutions are generic, robust and flexible and the experimental evaluation shows that both proposed approaches lead to significant energy savings while meeting the users' requirements

La communication mobile est considérée comme l'un des piliers des villes intelligentes, où les citoyens devraient pouvoir bénéficier des services de télécommunications partout et quand ils les souhaitent, d'une manière sûre et peu coûteuse. Cela est possible grâce à un déploiement dense des réseaux mobiles à large bande de dernière génération. Ce déploiement dense entraînera une consommation énergétique plus élevée et donc plus d'émissions de gaz et de pollution. Par conséquent, il est crucial d'un point de vue environnemental de réduire la consommation d'énergie. Dans le cadre de cette thèse, nous introduisons des méthodes dynamiques de gestion de ressources permettant d'augmenter le débit et l'efficacité énergétique, et réduisant ainsi la pollution. Ainsi, nous ciblons les réseaux multicellulaires verts où l'augmentation de l'efficacité énergétique doit tenir en compte de l'accroissement de la demande de débit par les utilisateurs mobiles. Cette augmentation, exponentielle en terme de débit, a poussé les opérateurs à utiliser la totalité du spectre fréquentiel dans toutes les cellules des réseaux mobiles de dernière génération. Par conséquence, l'interférence intercellulaire (ICI : Inter-Cell Interference) devient prépondérante et dégrade la performance des utilisateurs, en particulier ceux ayant de mauvaises conditions radios. Dans cette thèse, nous nous focalisons sur la technique du contrôle de puissance considérée comme une des méthodes clé de la coordination d'interférence Intercellulaire (ICIC : Inter-Cell Interference Coordination), tout en mettant l'accent sur des méthodes efficaces énergétiquement. Nous formulons ce problème d'allocation de la puissance, sur le lien descendant en mettant en œuvre des méthodes centralisées et décentralisées: les méthodes centralisées ayant recours à l'optimisation convexe alors que les méthodes décentralisées se basant sur la théorie des jeux non-coopératifs. Par ailleurs nous proposons ensuite une heuristique de contrôle de puissance qui a l'avantage d'être stable et basée sur des messages de signalisation déjà existant dans le système. Cette heuristique permet d'éviter le gaspillage de la bande passante par des signalisations intercellulaires et de réduire le ICI. De plus, le problème de contrôle de puissance a un impact important sur l'allocation des ressources radios et sur l'association des utilisateurs mobiles à une station de base. Ainsi, dans la deuxième partie de la thèse, nous avons formulé un problème globale englobant le contrôle de puissance, le contrôle d'allocation de ressources radios, et le contrôle de l'association des utilisateurs à une station de base, cela afin d'obtenir une solution globalement efficace. Ces trois sous problèmes sont traités itérativement jusqu'à convergence de la solution globale. En particulier nous proposons pour la problématique d'association des utilisateurs trois algorithmes: un algorithme centralisé, un algorithme semi-distribué et finalement un algorithme complètement distribué se basant sur l'apprentissage par renforcement. Par ailleurs, pour l'allocation de puissance, nous implémentons des solutions centralisées et des solutions distribuées. Les preuves de convergence des algorithmes ont été établies et les simulations approfondies ont permis d'évaluer et de comparer quantitativement les performances, l'efficacité énergétique et le temps de convergence des algorithmes proposés. / Mobile communication is considered as one of the building blocks of smart cities, where citizens should be able to benefit from telecommunications services, wherever they are, whenever they want, and in a secure and non-costly way. This can be done by dense deployment of the latest generation of mobile broadband networks. However, this dense deployment will lead to higher energy consumption, and thus more gas emission and pollution. Therefore, it is crucial from environmental point of view to propose solution reducing energy consumption. In this thesis, we introduce dynamic resource management methods that increase throughput and energy efficiency, and thus reduce pollution. In this framework, we are targeting green multi-cell networks where increased energy efficiency must take into account the increased demand of data by mobile users. This increase, which is exponential in terms of throughput, pushed operators to use the entire frequency spectrum in all cells of the latest generation of mobile networks. As a result, Inter-Cellular Interference (ICI) became preponderant and degraded the performance of users, particularly those with poor radio conditions. In this thesis, we focus on the techniques of power control on the downlink direction, which is considered as one of the key methods of Inter-Cell Interference Coordination (ICIC) while focusing on energy efficient methods. We propose centralized and decentralized methods for this problem of power allocation: centralized methods through convex optimization, and decentralized methods based on non-cooperative game theory. Furthermore, we propose a power control heuristic which has the advantage of being stable and based on signaling messages already existing in the system. The power control problem has a relevant impact on the allocation of radio resources and on the association of mobile users with their servicing Base Station. Therefore, in the second part of the thesis, we formulated a global problem encompassing power control, radio resources allocation, and control of users’ association to a base station. These three sub-problems are treated iteratively until the convergence to the overall solution. In particular, we propose three algorithms for the user association problem: a centralized algorithm, a semi-distributed algorithm and finally a fully distributed algorithm based on reinforcement learning. In addition, for power allocation we implement centralized solutions and distributed solutions. The proof of convergence for the various algorithms is established and the in-depth simulations allow us to evaluate and compare quantitatively the performance, the energy efficiency, and the convergence time of the proposed algorithms.