Dissertations / Theses on the topic 'Resource allocation'

Thesis (Ph. D.)--University of California, San Diego, 2010.
Title from first page of PDF file (viewed March 29, 2010). Available via ProQuest Digital Dissertations. Vita. Includes bibliographical references (p. 146-155).

En problemes d'assignació de recursos, normalment s'han de tenir en compte les incerteses que poden provocar canvis en les dades inicials. Aquests canvis dificulten l'aplicabilitat de les planificacions que s'hagin fet inicialment.
Aquesta tesi se centra en l'elaboració de tècniques que consideren la incertesa alhora de cercar solucions robustes, és a dir solucions que puguin continuar essent vàlides encara que hi hagi canvis en l'entorn. Particularment, introduïm el concepte de robustesa basat en reparabilitat, on una solució robusta és una que pot ser reparada fàcilment en cas que hi hagi incidències. La nostra aproximació es basa en lògica proposicional, codificant el problema en una fórmula de satisfactibilitat Booleana, i aplicant tècniques de reformulació per a la generació de solucions robustes. També presentem un mecanisme per a incorporar flexibilitat a les solucions robustes, de manera que es pugui establir fàcilment el grau desitjat entre robustesa i optimalitat de les solucions.
Resource allocation problems usually include uncertainties that can produce changes in the data of the problem. These changes may cause difficulties in the applicability of the solutions.
This thesis is focused in the elaboration of techniques that take into account such uncertainties while searching for robust solutions, i.e. solutions that can remain valid even if there are changes in the environment. Particularly, we introduce the concept of robustness based on reparability, where a robust solution is one that can be easily repaired when unexpected events occur. Our approach is based in propositional logic, encoding the problem to a Boolean formula, and applying reformulation techniques in order to generate robust solutions. Additionally, we present a mechanism to incorporate flexibility to the robust solutions, so that one can easily set the desired degree between optimality and robustness.

How should we divide a good or set of goods among a set of agents? There are various constraints that we can consider. We consider two particular constraints. The first is fairness - how can we find fair allocations? The second is truthfulness - what if we do not know agents valuations for the goods being allocated? What if these valuations need to be elicited, and agents will misreport their valuations if it is beneficial? Can we design procedures that elicit agents' true valuations while preserving the quality of the allocation? We consider truthful and fair resource allocation procedures through a computational lens. We first study fair division of a heterogeneous, divisible good, colloquially known as the cake cutting problem. We depart from the existing literature and assume that agents have restricted valuations that can be succinctly communicated. We consider the problems of welfare-maximization, expressiveness, and truthfulness in cake cutting under this model. In the second part of this dissertation we consider truthfulness in settings where payments can be used to incentivize agents to truthfully reveal their private information. A mechanism asks agents to report their private preference information and computes an allocation and payments based on these reports. The mechanism design problem is to find incentive compatible mechanisms which incentivize agents to truthfully reveal their private information and simultaneously compute allocations with desirable properties. The traditional approach to mechanism design specifies mechanisms by hand and proves that certain desirable properties are satisfied. This limits the design space to mechanisms that can be written down and analyzed. We take a computational approach, giving computational procedures that produce mechanisms with desirable properties. Our first contribution designs a procedure that modifies heuristic branch and bound search and makes it usable as the allocation algorithm in an incentive compatible mechanism. Our second contribution draws a novel connection between incentive compatible mechanisms and machine learning. We use this connection to learn payment rules to pair with provided allocation rules. Our payment rules are not exactly incentive compatibility, but they minimize a measure of how much agents can gain by misreporting.
Engineering and Applied Sciences

This thesis proposes a novel method for allocating multi-attribute computational resources via competing marketplaces. Trading agents, working on behalf of resource consumers and providers, choose to trade in resource markets where the resources being traded best align with their preferences and constraints. Market-exchange agents, in competition with each other, attempt to provide resource markets that attract traders, with the goal of maximising their profit. Because exchanges can only partially observe global supply and demand schedules, novel strategies are required to automate their search for market niches. By applying a novel methodology, which is also used to explore, for the first time, the generalisation ability of market mechanisms, novel attribute-level selection (ALS) strategies are analysed in competitive market environments. Results from simulation studies suggest that using these ALS strategies, market-exchanges can seek out market niches under a variety of environmental conditions. In order to facilitate traders' selection between dynamic competing marketplaces, this thesis explores the application of a reputation system, and simulation results suggest reputation-based market-selection signals can lead to more efficient global resource allocations in dynamic environments. Further, a subjective reputation system, grounded in Bayesian statistics, allows traders to identify and ignore the opinions of those attempting to falsely damage or bolster marketplace reputation.

Thesis (M.B.A.)--Massachusetts Institute of Technology, Sloan School of Management; and, (S.M.)--Massachusetts Institute of Technology, Dept. of Mechanical Engineering; in conjunction with the Leaders for Manufacturing Program at MIT, 2001.
Includes bibliographical references (p. 72-73).
by Quang Nguyen.
S.M.
M.B.A.

L'informatique en nuage (Cloud Computing) est un modèle à grande échelle et en évolution continue, permettant le provisionnement et l'utilisation des ressources informatiques à la demande, selon un modèle rentable de facturation à l'usage "pay-as-you-go". Ce nouveau paradigme a rapidement révolutionné l'industrie IT et a permis de nouvelles tendances en matière de prestation de services informatiques, y compris l'externalisation des infrastructures IT vers des prestataires tiers spécialisés. Cependant, la nature multi-utilisateur des plateformes d'hébergement, ainsi que la complexité des demandes, soulèvent plusieurs défis liés à la gestion des ressources Cloud. Malgré l'attention croissante portée à ce sujet, la plupart des efforts ont été axés sur des solutions centrées utilisateur, et malheureusement beaucoup moins sur les difficultés rencontrées par les fournisseurs pour maximiser leurs bénéfices. Dans ce contexte, la fédération de Cloud a été récemment proposée comme une solution clé pour répondre à l'augmentation et la fluctuation des charges de travail. Les fournisseurs ayant des besoins complémentaires en ressources au fil du temps, peuvent collaborer et partager leurs infrastructures respectives via l'externalisation ("Outsourcing") pour mieux satisfaire les demandes et exigences des utilisateurs. Cette thèse aborde le problème d'optimisation du profit via la fédération et l'allocation optimale des ressources parmi plusieurs fournisseurs d'infrastructures Cloud. L'étude examine les principaux défis et opportunités liés à la maximisation des revenus dans une fédération de Clouds, et définit des stratégies efficaces pour diriger les fournisseurs dans leurs décisions de coopération. Le but est de fournir des algorithmes qui automatisent la sélection du plan d'allocation le plus rentable, qui satisfait à la fois la demande des utilisateurs et les exigences de mise en réseau. Nous visons des modèles d'allocation génériques et robustes qui répondent aux nouvelles tendances Cloud, et de traiter les requêtes simples ainsi que complexes nécessitant le provisionnement de services composites avec différentes ressources distribuées et connectées. Conformément aux objectifs de la thèse, nous avons mené une étude approfondie des travaux antérieurs traitant la problématique de provisionnement des ressources d'infrastructure dans les environnements Cloud. L'analyse a porté notamment sur les modèles d'allocation ayant pour objectif la maximisation de profit et les lacunes et défis associés dans les fédérations de Clouds. Dans un deuxième temps, nous avons proposé un programme linéaire en nombre entiers (ILP), pour aider les fournisseurs de services dans leurs décisions de coopération via des actions optimales d'externalisation (outsourcing), d'internalisation (insourcing) et d'allocation en local. Ces différentes décisions d'allocation sont traitées conjointement dans une formule d'optimisation globale qui partitionne les graphes de requêtes entre les membres de la fédération, tout en satisfaisant les exigences de communication entre les services élémentaires. En plus de la topologie des graphes de ressources, ce partitionnement prend en compte les prix dynamiques et les quotas proposés par les membres de la fédération ainsi que les coûts d'hébergement des ressources et de leur mise en réseau. Enfin, nous avons proposé un algorithme heuristique pour améliorer les temps de convergence avec les instances de problèmes à grande échelle. L'approche proposée utilise un algorithme de "clustering" basé sur les arbres de Gomory-Hu pour le partitionnement des graphes et une stratégie de meilleur ajustement (Best-Fit matching) pour l'allocation et le placement des sous-graphes résultants. L'utilisation conjointe de ces deux techniques permet de capturer l'essence du problème d'optimisation et de respecter les différents objectifs fixés, tout en améliorant le temps de convergence vers les solutions quasi-optimales de plusieurs ordres de grandeur
Cloud computing is a steadily maturing large-scale model for providing on-demand IT resources on a pay-as-you-go basis. This emerging paradigm has rapidly revolutionized the IT industry and enabled new service delivery trends, including infrastructure externalization to large third-party providers. The Cloud multi-tenancy architecture raises several management challenges for all stakeholders. Despite the increasing attention on this topic, most efforts have been focused on user-centric solutions, and unfortunately much less on the difficulties encountered by Cloud providers in improving their business. In this context, Cloud Federation has been recently suggested as a key solution to the increasing and variable workloads. Providers having complementary resource requirements over time can collaborate and share their respective infrastructures, to dynamically adjust their hosting capacities in response to users' demands. However, joining a federation makes the resource allocation more complex, since providers have to also deal with cooperation decisions and workload distribution within the federation. This is of crucial importance for cloud providers from a profit standpoint and especially challenging in a federation involving multiple providers and distributed resources and applications. This thesis addresses profit optimization through federating and allocating resources amongst multiple infrastructure providers. The work investigates the key challenges and opportunities related to revenue maximization in Cloud federation, and defines efficient strategies to govern providers' cooperation decisions. The goal is to provide algorithms to automate the selection of cost-effective distributed allocation plans that simultaneously satisfy user demand and networking requirements. We seek generic and robust models able to meet the new trends in Cloud services and handle both simple and complex requests, ranging from standalone VMs to composite services requiring the provisioning of distributed and connected resources. In line with the thesis objectives, we first provide a survey of prior work on infrastructure resource provisioning in Cloud environments. The analysis mainly focuses on profit-driven allocation models in Cloud federations and the associated gaps and challenges with emphasis on pricing and networking issues. Then, we present a novel exact integer linear program (ILP), to assist IaaS providers in their cooperation decisions, through optimal "insourcing", "outsourcing" and local allocation operations. The different allocation decisions are treated jointly in a global optimization formulation that splits resource request graphs across federation members while satisfying communication requirements between request subsets. In addition to the request topology, this partitioning takes into account the dynamic prices and quotas proposed by federation members as well as the costs of resources and their networking. The algorithm performance evaluation and the identified benefits confirm the relevance of resource federation in improving providers' profits and shed light into the most favorable conditions to join or build a federation. Finally, a new topology-aware allocation heuristic is proposed to improve convergence times with large-scale problem instances. The proposed approach uses a Gomory-Hu tree based clustering algorithm for request graphs partitioning, and a Best-Fit matching strategy for subgraphs placement and allocation. Combining both techniques captures the essence of the optimization problem and meets the objectives, while speeding up convergence to near-optimal solutions by several orders of magnitude

L'informatique en nuage (Cloud Computing) est un modèle à grande échelle et en évolution continue, permettant le provisionnement et l'utilisation des ressources informatiques à la demande, selon un modèle rentable de facturation à l'usage "pay-as-you-go". Ce nouveau paradigme a rapidement révolutionné l'industrie IT et a permis de nouvelles tendances en matière de prestation de services informatiques, y compris l'externalisation des infrastructures IT vers des prestataires tiers spécialisés. Cependant, la nature multi-utilisateur des plateformes d'hébergement, ainsi que la complexité des demandes, soulèvent plusieurs défis liés à la gestion des ressources Cloud. Malgré l'attention croissante portée à ce sujet, la plupart des efforts ont été axés sur des solutions centrées utilisateur, et malheureusement beaucoup moins sur les difficultés rencontrées par les fournisseurs pour maximiser leurs bénéfices. Dans ce contexte, la fédération de Cloud a été récemment proposée comme une solution clé pour répondre à l'augmentation et la fluctuation des charges de travail. Les fournisseurs ayant des besoins complémentaires en ressources au fil du temps, peuvent collaborer et partager leurs infrastructures respectives via l'externalisation ("Outsourcing") pour mieux satisfaire les demandes et exigences des utilisateurs. Cette thèse aborde le problème d'optimisation du profit via la fédération et l'allocation optimale des ressources parmi plusieurs fournisseurs d'infrastructures Cloud. L'étude examine les principaux défis et opportunités liés à la maximisation des revenus dans une fédération de Clouds, et définit des stratégies efficaces pour diriger les fournisseurs dans leurs décisions de coopération. Le but est de fournir des algorithmes qui automatisent la sélection du plan d'allocation le plus rentable, qui satisfait à la fois la demande des utilisateurs et les exigences de mise en réseau. Nous visons des modèles d'allocation génériques et robustes qui répondent aux nouvelles tendances Cloud, et de traiter les requêtes simples ainsi que complexes nécessitant le provisionnement de services composites avec différentes ressources distribuées et connectées. Conformément aux objectifs de la thèse, nous avons mené une étude approfondie des travaux antérieurs traitant la problématique de provisionnement des ressources d'infrastructure dans les environnements Cloud. L'analyse a porté notamment sur les modèles d'allocation ayant pour objectif la maximisation de profit et les lacunes et défis associés dans les fédérations de Clouds. Dans un deuxième temps, nous avons proposé un programme linéaire en nombre entiers (ILP), pour aider les fournisseurs de services dans leurs décisions de coopération via des actions optimales d'externalisation (outsourcing), d'internalisation (insourcing) et d'allocation en local. Ces différentes décisions d'allocation sont traitées conjointement dans une formule d'optimisation globale qui partitionne les graphes de requêtes entre les membres de la fédération, tout en satisfaisant les exigences de communication entre les services élémentaires. En plus de la topologie des graphes de ressources, ce partitionnement prend en compte les prix dynamiques et les quotas proposés par les membres de la fédération ainsi que les coûts d'hébergement des ressources et de leur mise en réseau. Enfin, nous avons proposé un algorithme heuristique pour améliorer les temps de convergence avec les instances de problèmes à grande échelle. L'approche proposée utilise un algorithme de "clustering" basé sur les arbres de Gomory-Hu pour le partitionnement des graphes et une stratégie de meilleur ajustement (Best-Fit matching) pour l'allocation et le placement des sous-graphes résultants. L'utilisation conjointe de ces deux techniques permet de capturer l'essence du problème d'optimisation et de respecter les différents objectifs fixés, tout en améliorant le temps de convergence vers les solutions quasi-optimales de plusieurs ordres de grandeur
Cloud computing is a steadily maturing large-scale model for providing on-demand IT resources on a pay-as-you-go basis. This emerging paradigm has rapidly revolutionized the IT industry and enabled new service delivery trends, including infrastructure externalization to large third-party providers. The Cloud multi-tenancy architecture raises several management challenges for all stakeholders. Despite the increasing attention on this topic, most efforts have been focused on user-centric solutions, and unfortunately much less on the difficulties encountered by Cloud providers in improving their business. In this context, Cloud Federation has been recently suggested as a key solution to the increasing and variable workloads. Providers having complementary resource requirements over time can collaborate and share their respective infrastructures, to dynamically adjust their hosting capacities in response to users' demands. However, joining a federation makes the resource allocation more complex, since providers have to also deal with cooperation decisions and workload distribution within the federation. This is of crucial importance for cloud providers from a profit standpoint and especially challenging in a federation involving multiple providers and distributed resources and applications. This thesis addresses profit optimization through federating and allocating resources amongst multiple infrastructure providers. The work investigates the key challenges and opportunities related to revenue maximization in Cloud federation, and defines efficient strategies to govern providers' cooperation decisions. The goal is to provide algorithms to automate the selection of cost-effective distributed allocation plans that simultaneously satisfy user demand and networking requirements. We seek generic and robust models able to meet the new trends in Cloud services and handle both simple and complex requests, ranging from standalone VMs to composite services requiring the provisioning of distributed and connected resources. In line with the thesis objectives, we first provide a survey of prior work on infrastructure resource provisioning in Cloud environments. The analysis mainly focuses on profit-driven allocation models in Cloud federations and the associated gaps and challenges with emphasis on pricing and networking issues. Then, we present a novel exact integer linear program (ILP), to assist IaaS providers in their cooperation decisions, through optimal "insourcing", "outsourcing" and local allocation operations. The different allocation decisions are treated jointly in a global optimization formulation that splits resource request graphs across federation members while satisfying communication requirements between request subsets. In addition to the request topology, this partitioning takes into account the dynamic prices and quotas proposed by federation members as well as the costs of resources and their networking. The algorithm performance evaluation and the identified benefits confirm the relevance of resource federation in improving providers' profits and shed light into the most favorable conditions to join or build a federation. Finally, a new topology-aware allocation heuristic is proposed to improve convergence times with large-scale problem instances. The proposed approach uses a Gomory-Hu tree based clustering algorithm for request graphs partitioning, and a Best-Fit matching strategy for subgraphs placement and allocation. Combining both techniques captures the essence of the optimization problem and meets the objectives, while speeding up convergence to near-optimal solutions by several orders of magnitude

La tesis presenta una aproximació a un conjunt de tècniques per permetre l'extensió de les capacitats computacionals, sota demanada, en comunitats formades per usuaris d'Internet que volen agregar els seus recursos per aconseguir una finalitat comuna. Aquest tipus de comunitats, emergeixen com a noves formes d'organització gràcies a l'increment de les capacitats computacionals i l'ampla de banda. La computació voluntaria com la que es dona en sistemes com SETI@home, Grids col.laboratius com OurGrid o LaCOLLA, Ad-hoc i Grids d'igual a igual com P-Grid o X-Grid d'Apple, Grids Oberts com els adreçats per SORMA o Grid4All i moltes d'altres formes de computació Grid basades en agrupació de recursos en forma d'Organitzacions Virtuals són l'objectiu d'aquest treball. Aquests sistems es caracteritzen pel propòsit dels seus participants, és a dir, dur a terme un objectiu comú fent ús de l'agregació dels sesus propis recursos. Els sistemes esmentats, contrariament als sistemes Grid d'alt rendiment computacional, són oberts a nous participants fet que els converteix en escenaris inpredictibles, dinàmics i on els recuros poden connectar-se i desconnectar-se de forma espontànea. Mentre que l'aspecte crític dels Grids d'altes prestacions és el rendiment computacional, l'estabilitat i la disponibilitat són els aspectes més importants en els sistemes adrec cats en aquest treball. La tesis homogeinitza els conceptes dels paradigmes anteriors sota el nom de Sistemes Contributius, nom que és usat al llarg de la dissertació per referir-nos a sistemes en els quals els seus usuaris fan contribució dels seus recursos per tal que aquest siguin usats de forma col.lectiva i axií aconseguir un objectiu comú. L'expansió de recursos en els Sistemes Contributius és una funcionalitat requerida per tal de augmentar les limitades capacitats computacionals dels grups col.laboratius formats de forma ad-hoc. Sobretot en moments puntuals quan els recursos necessaris són majors que els disponibles en el grup. Quatre aspectes s'adressen al llarg de la dissertació. Primer, les propietats i principals applicacions dels Sistemes Contributius són identificades, així com es motiva la necessitat d'infraestructures que permetin l'expansió de recursos computacionals sota demanda. Aquestes idees van en la direcció de l'Utility Computing, emergents línies de negoci de les principals companyies de la IT. D'aquesta manera, la tesis proposa la provisió de recursos computacionals sota demanda a aquelles organitzacions que en necessitin, mitjanc cant l'agregació de recursos dels extrems d'Internet, ja siguin usuaris finals de la xarxa, altres organitzacions virtuals o proveidors de recursos. En aquest treball, l'assignació de recursos es gestionada per models de mercat ja que proveixen de mecanismes eficients i simples per gestionar l'assignació de recursos. Aquesta proposta aporta noves oportunitats als usuaris finals d'Internet per tal d'establir el seu negoci a la xarxa mitjanc cant la venda dels seus recursos no usats. A més a més aquest treball dona l'oportunitat a communitats petites a creixer i a portar capacitats de super-computació als usuaris finals d'Internet. En segon lloc, la tesis descriu semànticament els recursos computacionals per tal de constru"ir una base comú de coneixement sobre els recursos d'Internet. La descripció semàntica dels recursos permet un enteniment comú de la naturalesa dels recursos, permetent així l'agrupació i agregació de diferents tipus de tecnologíes mentre es mantenen la mateixa semàntica. Una base semàntica comú permet que aplicacions i sistemes de gestió de recursos siguin independents de la naturalesa real dels recursos. En aquest treball considerem com a aspecte fonamental aillar la gestió dels recursos de la seva naturalesa específica. La descripció semàntica a més permet el desenvolupament de especificacions genèriques que ens permeten definir els requeriments dels usuaris en sistemes d'assignació de recursos basats en mercats computacionals. Tercer, arquitectures que permeten l'expansió de recursos computacionals sota demanda en Sistemes Contributius són presentades. Aquestes arquitectures han estat especialment dissenyades per prove"ir de recursos computacionals mitjanc cant mercats a escenaris caracteritzats pel dinamisme, evolució i heterogene"itat dels seus recursos. L'arquitectura aporta les principals funcionalitats orientades a l'assignació de recursos mitjanc cant subhastes i permet a més a més l'execució d'aquests mercats sota demanda. Finalment, es presenta un mecanisme de mercat adaptat a l'assignació de recursos computacionals. Aquesta contribució es motiva pel fet que no existeix fins avui cap mecanisme que permeti l'assignació efficient de recursos computacionals en que la seva única diferència és la unitat de temps en la que s'ofereixen. La tesis construeix un camí per assolir l'expansió de recursos computacionals de forma flexible i decentralitzada en comunitats on els recursos són compartits pels seus participants. Aquest camí es construeix mitjanc cant l'anàlisis dels escenaris d'aplicació, l'estudi i definició de models semàntics que permeten la descripció dels recursos computacionals, proposant també arquitectures flexibles i configurables que permeten aconseguir l'expansió dels recursos computacionals sota demanda i proposant mecanismes de mercat adaptats a tal escenari.
The thesis presents an approach to on-demand capacity expansion in communities of Internet users that aggregate their resources to achieve a common objective. Such commu- nities are emerging as forms of organisation taking advantage of an increasing broadband access and computational capacity. Volunteer computing such as SETI@home, Collab- orative Grids such as OurGrid and LaCOLLA, Ad-hoc and Peer-to-Peer Grids, such as P-Grid and the XGrid project from Apple, Open Grids such as those addressed by SORMA and Grid4All and many other approaches of Grid Computing based on Virtual Organisa- tions are the focus of our work. These systems are characterised by the purpose of their participants, i.e. to achieve a common objective taking advantage of the aggregation of other resources. The cited systems, in contrast to high performance computing Grids, are open to new participants, which makes their behaviour unpredictable and dynamic, and resources are usually connected and disconnected spontaneously. While the critical aspect of high performance Grids is computational performance, stability and availability are the main issues for the systems addressed in this work. The thesis homogenises the concepts of those paradigms under the term Contributory System, which is used throughout the thesis to refer to the systems where users provide their resources to be used collectively to achieve a common objective. Resource expan- sion in Contributory Systems is required so as to increase the limited capacities of ad-hoc collaborative groups under unexpected load surges, temporary resource requirements or other policies defined by the objectives of the Virtual Organisation that they constitute. Four aspects are addressed by the dissertation. Firstly, it identifies the main properties and applications of Contributory Systems and motivates the need for infrastructures to enable on-demand resource expansion. This goes in the direction of Utility Computing trends which are main business lines for IT companies. Thus the thesis proposes the on-demand provision of idle resources from the extremes of the Internet, other Virtual Or- ganisations or Resource Providers to those organisations that have resource needs. In this work, resource allocation is handled by market models which provide efficient while simple mechanisms to mediate the allocation of resources. This proposal enables new emerging opportunities to Internet users to make their business on the Internet by selling their idle resources. Besides, this brings the opportunity to small communities to grow and to bring super-computing capacities to Internet end-users. Secondly, the thesis describes semantically Computational Resources so as to build a common knowledge about the Internets resources. The semantic description enables a common understanding of the nature of resources, permitting the pooling and aggrega- tion of distinct types of technologies while maintaining the same semantics. This makes applications and resource management frameworks independent of the real nature of the resources which we claim as a fundamental aspect to keep resource management indepen- dent of the dynamics and evolution of technology in computational environments, such as in Contributory Systems. A semantic description permits the development of generic specifications to provide bid and offer descriptions in computational markets. Thirdly, the architecture for on-demand resource expansion in Contributory Systems is presented. It has been designed to provide the main functionalities to on-demand provi- sion of resources through markets to scenarios characterized by dynamism, evolution and heterogeneity. The architecture provides the main market oriented functionalities and en- ables dynamic and on-demand execution of market mechanisms. Finally, a specific Grid-oriented market mechanism is presented. The approach is moti- vated due to the unsuitability of current auctions to efficiently allocate time-differentiated resources (usually provided by many different resource providers) such as most of the re- sources in a Contributory System. The thesis builds a roadmap to achieve flexible and decentralized resource expansion in communities where resources are shared by their participants by analysing the main scenarios where it can be applied, providing the semantics and specification to enable the description of the user's requirements, proposing a flexible and configurable architecture to deal with on-demand resource expansion in Virtual Organisations and proposing an specific mechanism adapted to trade computational resources.

In this thesis we investigate different algorithms for dynamic resource allocation in wireless networks. We introduce a general framework for modeling systems whichis applicable to many scenarios. We also analyze a specific scenario with adaptivebeamforming and show how it fits into the proposed framework. We then studytwo different resource allocation problems: Quality-of-Service (QoS) constraineduser scheduling and sum-rate maximization. For user scheduling, we select some“good” set of users that is allowed to use a specific resource. We investigatedifferent algorithms with varying complexities. For the sum-rate maximizationwe find the global optimum through an algorithm that takes advantage of thestructure of the problem by reformulating it as a D.C. program, i.e., a minimizationover a difference of convex functions. We validate this approach by showing that itis more efficient than an exhaustive search at exploring the space of solutions. Thealgorithm provides a good benchmark for more suboptimal algorithms to comparewith. The framework in which we construct the algorithm, apart from being verygeneral, is also very flexible and can be used to implement other low complexitybut suboptimal algorithms.

This thesis presents several efficient and adaptive resource allocation schemes in wireless networks under the framework of Markov Decision Problem (MDP). In particular, we formulate meaningful trade-offs for three specific resource allocation problems as MDPs and show that their solutions exhibit certain special structures. In each case, by utilizing the underlying structure, we present a resource allocation solution that is computationally inexpensive and is scalable in terms of the system parameters. First, we present opportunistic algorithms in scheduling High Speed Downlink Packet Access (HSDPA) users that exploit channel and buffer variations to increase the probability of uninterrupted media play-out. We formulate a feasibility problem with stability and robustness Quality-of-Service (QoS) constraints. A methodology for obtaining a feasible solution is proposed by starting with a stable algorithm that satisfies the stability QoS constraints. Next, we present optimal adaptive modulation and coding policies that minimize the transmission latency and modulation/coding switching cost across finite-state Markovian fading channels. The optimal tradeoff between the transmission delay and the switching costs is formulated as a discounted cost infinite horizon MDP. We show that under certain sufficient conditions optimal modulation and coding selection policies are monotone in the state variables. Finally, we present an ARQ-based power and retransmission control policy that achieves an optimal tradeoff between transmission power, delay, and packet drop penalty costs. Under certain sufficient conditions, we show that the optimal power and retransmission control policies are monotone in the channel quality, the penalty cost, and the number of the retransmission slots left.
Applied Science, Faculty of
Electrical and Computer Engineering, Department of
Graduate

The subject of this thesis is the concept of market-oriented programming and market protocols. We want to solve an allocation problem where some resources are to be divided among a number of agents. Each agent has a utility function telling how much the current allocation is worth for it. The goal is to allocate the resources among the agents in a way that maximizes the sum of the utilities of all agents. To solve this problem we use the concept of markets to create mechanisms for computational implementation. To achieve the advantages of market-oriented programming, we have to consider the conceptual view of the problem a main design issue. We want to investigate the possibilities to build computationally effective mechanisms which maintain the intuitive, easy-to-understand structure of market-based approaches. In the first paper we look at two examples from the literature and show that conceptual improvements of the approaches will make agent behavior more realistic. This will also make the examples fit into a more general theory. In the second paper we create a market mechanism for handling combinatorial markets. The mechanism includes an auction, where each iteration runs in polynomial time. The mechanism shows good performance when the number of resources is relatively small compared to the number of agents.

Resource allocation consists in allocating spectrum and power on every link of a network, possibly under power and rate requirements. In the context of cognitive radios, almost 15 years of research produced an impressive amount of theoretical contributions, exploring a wide range of possibilities. However, despite the ever-growing list of imaginable scenarios, we observe in Chapter 2 that most of these studies are based on similar working hypotheses. Our first contribution is to challenge some of these hypotheses, and propose a novel resource allocation scheme. Sticking to realistic assumptions, we show how our scheme reduces both computational complexity and control traffic, compared to other state-of-the-art techniques.

Due to a majority of the abovementioned studies making some constraining assumptions, realistic system designs and experimental demonstrations are much more quiet and unharvested fields. In an effort to help this transition from theory to practice, our second contribution is a four-nodes cognitive network demonstrator, presented in Chapter 3. In particular, we aim at providing a modular platform available for further open collaboration: different options for spectrum sensing, resource allocation, synchronisation and others can be experimented on this demonstrator. As an example, we develop a simple protocol to show that our proposed resource allocation scheme is fully implementable, and that primary users can be avoided using our approach.

Chapter 4 aims at removing another working hypothesis made when developping our resource allocation scheme. Indeed, resource alloca- tion is traditionally a Media Access Control (MAC) layer problem. This means that when solving a resource allocation problem in a network, the routing paths are usually assumed to be known. Conversely, the routing problem, which is a network layer issue, usually assumes that the available capacities on each link of the network (which depend on resource allocation) are known. Nevertheless, these two problems are mathematically entangled, and a cross-layer allocation strategy can best decoupled approaches in several ways, as we discuss in Chapter 4. Accordingly, our third and last contribution is to develop such a cross-layer allocation scheme for the scenario proposed in previous chapters.

All conclusions are summarised in Chapter 5, which also points to a few tracks for future research.
Doctorat en Sciences de l'ingénieur
info:eu-repo/semantics/nonPublished

In this thesis, resource allocation problems relevant to multicarrier DSL environments are considered. The resources in a multicarrier DSL environment are bandwidth (i.e., subcarriers), the power allocated, the bits loaded and possibly the coding scheme used on each subcarrier. The major impairments in DSL environments are crosstalk and external noise . Crosstalk (predictable and controllable) is the interference caused by other DSL users sharing the same medium. External Noise (unpredictable and uncontrollable) consists of relatively high energy bursts due to electromagnetic interference from physical phenomena, electrical switches, motors and home appliances which are invariably present in the close vicinity of DSL modems.
In current DSL applications, Crosstalk is kept in control by specifying a fixed peakpower constraint (based on the worst-case) which each user has to obey---a technique known as Static Spectrum Management (SSM). This simplifies the resource allocation to a single-user optimization problem. But the worst-case peak power constraint is overly restrictive and results in poorer rates. Recently Dynamic Spectrum Management (DSM) techniques which dynamically vary the multiuser power allocation for crosstalk control instead of using fixed peak power constraint have proven to provide much better rates. This improvement however comes at the cost of dealing with a more complicated multiuser optimization problem.
On the other hand, due to its unpredictability, external noise (and RFI pickup) has been combated with the use of a suitable safety margin.
Based on application and scenario, Resource Allocation is either performed with the objective of Rate maximization (at a fixed margin) or Margin maximization (at a fixed rate) since each of the quantities indirectly imposes a cap on the other.
But in both rate maximizing and margin maximizing resource allocation algorithms available in literature the bits loaded were always constrained to integers because most scalable modulation schemes such as QAM or PSK support integer bit/symbol. It was initially believed that most (not all) of the granularity losses (due to the integer bit constraint) could be recovered through 'bit-rounding' and 'energy re-scaling'. But this was observed only for the total power constrained case. With the advent of peak power constraint, we show that the room for optimization in the energy domain is severely restricted and granularity losses constitute a significant percentage of the achievable data rate. To recover these losses, we propose the Adaptive Reed Solomon aided Fine Granularity Loading (ARSFGL) scheme---a scheme that jointly optimizes the power, bit and code allocation. For achieving near-continuous rate adaptation, the family of Reed Solomon (RS) codes has been used for their low redundancy, high flexibility in correction capability and highly programmable architecture. Simulation results with realistic VDSL-DMT systems with the currently standardized SSM framework show more than 20% improvement in rate achieved for most cases.
The extension of ARSFGL technique to multiuser (DSM) scenarios results in a purely distributed scheme which provides rates better or equal to the rates achieved by the centralized, optimal (much more complicated) multiuser integer-bit loading scheme.
Further in this work a multiuser margin maximization algorithm is developed. Near-continuous rates provided by the ARSFGL scheme allow continuous bit loading assumption for simplicity. Prior to this work, no multiuser margin maximization algorithm existed, even though the importance of margin maximization is well-recognized. Most existing single-user margin maximization algorithms rely on a fixed crosstalk assumption. But in multiuser (DSM) scenarios each user's power allocation dynamically determines other user's crosstalk. With direct extension of single-user algorithms in multiuser (DSM) scenarios, one user's margin maximization can lead to the failure of other users in meeting their target rates .
We begin by exploring the favorable monotonicity and fairness properties that multi-user margin exhibits over a multiuser rate region and use them to formulate a box-constrained non-linear least squares (NLSQ) problem that can be solved by using a scaled gradient trust region approach with Broyden Jacobian update. This algorithm efficiently converges to a solution providing the best common equal margin to all users while explicitly guaranteeing that each user's target rate requirement is satisfied. The algorithm requires only minimal coordination among users, which makes it suitable for practical implementation.

When people multi-task with inputs that demand attention, processing, andencoding, sensory interference is possible at almost any level. Multiple Resource Theory (MRT) suggests that such interference may be avoided by drawing from separate pools of resources available when using different sensory channels, memory processes, and even different response modes. Thus, there should be advantages in dividing tasks among different sensory channels to tap independent pools of attentional resources. For example, people are better with two tasks using the eye and ear, than when using two auditory or two visual inputs. The majority of the research on MRT involves visual to auditory comparisons, i.e., the prime distance senses. The unstated implication is that the theory can be easily applied to other sensory systems, such as touch, but this is untested. This overlooks the fact that each sensory system has different characteristics that can influence how information processing is allocated in a multiple-task environment. For example, vision requires a directed gaze that is not required for sound or touch. Testing MRT with touch, not only eliminates competing theories, but helps establish its robustness across the senses. Three experiments compared the senses of touch and hearing to determine if the characteristics of those sensory modalities alter the allocation of processing resources. Specifically, it was hypothesized that differences in sensory characteristics would affect performance on a simple targeting task. All three experiments used auditory shadowing as the dual task load. In the first and third experiments a target was placed to the left or right of the participant and the targeting cue (either tactile, auditory, or combined) used to locate the target originated from the side on which the target was located. The only difference between experiments 1 and 3 was that in experiment 1 the auditory targeting cue was delivered by headphones, while in experiment 3 it was delivered by speakers. Experiment 2 was more difficult both in auditory perception and in processing. In this study the targeting cues came from in front of or behind the participant. Cues coming from in front of the participant meant the target was to the left, and conversely if the cue came from behind it meant that the target was to the right. The results of experiments 1 and 3 showed that when the signals originated from the sides, there was no difference in performance between the auditory and tactile targeting cues, whether by proximal or distal stimulation. However, in experiment 2, the participants were significantly slower to locate the target when using the auditory targeting cue than when using the tactile targeting cue, with nearly twice the losses when dual-tasking. No significant differences were found on performance of the shadowing task across the three experiments. The overall findings support the hypothesis that the characteristics of the sensory system itself influence the allocation of processing resources. For example, the differences in experiment 2 are likely due to front-back reversal, a common problem found with auditory stimuli located in front of or behind, but not with tactile stimuli.
Ph.D.
Department of Psychology
Arts and Sciences
Psychology

Thesis (S.B. and M.Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1999.
Includes bibliographical references (leaf 39).
by George S. Dolina.
S.B.and M.Eng.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Aeronautics and Astronautics, 2012.
Cataloged from department-submitted PDF version of thesis. This electronic version was submitted and approved by the author's academic department as part of an electronic thesis pilot project. The certified thesis is available in the Institute Archives and Special Collections.
Includes bibliographical references (p. 167-176).
The overarching goals of this thesis are to quantify the efficiency loss due to market participant strategic behavior, and to design proper pricing mechanisms that reduce the efficiency loss. The concept of efficiency loss is intimately related to the concept of "price of anarchy," which was advanced by Koutsoupias and Papadimitriou, and compares the maximum social welfare with that achieved at a worst Nash equilibrium. This thesis focuses on the following two topics: (i) For a market with an arbitrary number of participants, how much is the Nash equilibrium close, in the sense of price of anarchy, to a social optimum? (ii) For a resource allocation/pricing mechanism, is the social welfare achieved at an economic equilibrium asymptotically optimal, as the number of market participants goes to infinity? Regarding the first topic, we quantify the efficiency loss in classical Cournot oligopoly games, where multiple oligopolists compete by choosing quantities. We also compare the total profit earned at a Cournot equilibrium to the maximum possible total profit that would be obtained if the suppliers were to collude. For the second topic, related to the efficiency in large economics, we analyze the efficiency of Kelly's proportional allocation mechanism in large-scale wireless communication systems. We study a corresponding Bayesian game in which each user has incomplete information on the state or type of the other users, and show that the social welfare achieved at a Bayes-Nash equilibrium is asymptotically optimal, as the number of users increases to infinity. Finally, for electricity delivery systems, we propose a new dynamic pricing mechanism that explicitly encourages consumers to adapt their consumption so as to offset the variability of demand on conventional units. Through a dynamic game-theoretic formulation, we show that the proposed pricing mechanism achieves social optimality asymptotically, as the number of consumers increases to infinity.
by Yunjian Xu.
Ph.D.

Dans cette thèse nous étudierons l’allocation de puissance optimale pour des systèmes de communication multi utilisateur en lien ascendant. L’ordre de décodage et l’allocation de puissance optimaux pour minimiser la consommation totale de puissance sont déterminés lorsque les utilisateurs ont des contraintes de débit et que la suppression d’interférence est utilisée dans la station de base. De plus, nous chercherons à déterminer dans quelles conditions il est possible de faire une allocation distribuée en ne se basant que sur les connaissances statistiques du système. Par la suite nous considérerons les systèmes a entrées multiples sorties multiples, afin d’obtenir les matrices de précodage optimales pour que chaque utilisateur maximise son taux de transmission ergodique avec la seule connaissance des statistiques des canaux. Les bénéfices de l’utilisation d’un signal de coordination et de décodages successifs sont analysés. Ensuite, nous considérerons un scénario dans lequel les terminaux mobiles ont la possibilité de se connecter simultanément à plusieurs stations de base en utilisant des bandes de fréquence non superposées. L’allocation de puissance optimale est dérivée pour différents types de récepteurs et un algorithme itératif est proposé pour obtenir l’allocation optimale. Finalement, nous considérerons les contrôles d’accès au canal décentralisé entre utilisateurs choisis aléatoirement parmi une population nombreuse, avec de nombreuses interactions entre paires d’utilisateurs où les utilisateurs sont en concurrence pour une opportunité d’accès. Le choix du niveau de puissance est fait par chaque utilisateur, et nous analyserons à la fois les scénarios d’équipe et non coopératifs
In this thesis we study the subject of resource allocation for uplink communication systems. When users have target rate constraints and interference cancelation is used at the base station we provide the optimal decoding order and power allocation in order to minimize the power consumption. In addition conditions are derived under which the allocation can be done in a distributed way, with only some knowledge of the statistics of the system. We then proceed to consider multiple-input multiple-output (MIMO) systems, and obtain the optimal precoding matrices such that each user maximizes its own ergodic transmission rate from the sole knowledge of the overall channel statistics. The benefits of using a coordination signal and successive decoding are analyzed. Next, a scenario in which mobile terminals can be simultaneously connected to several base stations, using non-overlapping frequency bands is considered. The optimal power allocation in terms of sum rate is derived for different receiver types and an iterative algorithm proposed to achieve the optimal allocation. Finally, we consider decentralized medium-access control in which many pairwise interactions, where users compete for a medium access opportunity, occur between randomly selected users that belong to a large population. The choice of power level is done by each user, and both team and noncooperative scenarios are analyzed

Unlike the centralized network, the ad hoc network does not have any central administrations and energy is constrained, e.g. battery, so the resource allocation plays a very important role in efficiently managing the limited energy in ad hoc networks. This thesis focuses on the resource allocation in ad hoc networks and aims to develop novel techniques that will improve the network performance from different network layers, such as the physical layer, Medium Access Control (MAC) layer and network layer. This thesis examines the energy utilization in High Speed Downlink Packet Access (HSDPA) systems at the physical layer. Two resource allocation techniques, known as channel adaptive HSDPA and two-group HSDPA, are developed to improve the performance of an ad hoc radio system through reducing the residual energy, which in turn, should improve the data rate in HSDPA systems. The channel adaptive HSDPA removes the constraint on the number of channels used for transmissions. The two-group allocation minimizes the residual energy in HSDPA systems and therefore enhances the physical data rates in transmissions due to adaptive modulations. These proposed approaches provide better data rate than rates achieved with the current HSDPA type of algorithm. By considering both physical transmission power and data rates for defining the cost function of the routing scheme, an energy-aware routing scheme is proposed in order to find the routing path with the least energy consumption. By focusing on the routing paths with low energy consumption, computational complexity is significantly reduced. The data rate enhancement achieved by two-group resource allocation further reduces the required amount of energy per bit for each path. With a novel load balancing technique, the information bits can be allocated to each path in such that a way the overall amount of energy consumed is minimized. After loading bits to multiple routing paths, an end-to-end delay minimization solution along a routing path is developed through studying MAC distributed coordination function (DCF) service time. Furthermore, the overhead effect and the related throughput reduction are studied. In order to enhance the network throughput at the MAC layer, two MAC DCF-based adaptive payload allocation approaches are developed through introducing Lagrange optimization and studying equal data transmission period.

The IEEE 802.16 standard popularly known as WiMAX is at the forefront of the technological drive. Achieving high system throughput in these networks is challenging due to interference which limits concurrent transmissions. In this thesis, we study routing and link scheduling inWiMAX mesh networks. We present simple joint routing and link scheduling algorithms that have outperformed most of the existing proposals in our experiments. Our session based routing and links scheduling produced results approximately 90% of a trivial lower bound. We also study the problem of quality of service (QoS) provisioning in WiMAX mesh networks. QoS has become an attractive area of study driven by the increasing demand for multimedia content delivered wirelessly. To accommodate the different applications, the IEEE 802.16 standard defines four classes of service. In this dissertation, we propose a comprehensive scheme consisting of routing, link scheduling, call admission control (CAC) and channel assignment that considers all classes of service. Much of the work in the literature considers each of these problems in isolation. Our routing schemes use a metric that combines interference and traffic load to compute routes for requests while our link scheduling ensures that the QoS requirements of admitted requests are strictly met. Results from our simulation indicate that our routing and link scheduling schemes significantly improve network performance when the network is congested.
ix, 77 leaves : ill. ; 29 cm

This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.
Thesis: Ph. D. in Engineering Systems, Massachusetts Institute of Technology, School of Engineering, Institute for Data, Systems, and Society, 2019
Cataloged from student-submitted PDF version of thesis.
Includes bibliographical references (pages 139-150).
Networks are essential modeling tools in engineering, business, and public policy research. They can represent physical connections, such as manufacturing processes. They can be relationships among people, such as patient treatment in healthcare. They can also represent abstract interactions, such as the biological reaction between a certain vaccine and a certain virus. In this work, we bring several seemingly disparate problems under the same modeling framework, and show their thematic coherence via the angle of dynamic optimization on networks. Our research problems are drawn from business risk management, public health security, and public policy on vaccine selection. A common theme is the integrative design of (1) strategic resource placement on a network, and (2) operational deployment of such resources. We outline the research questions, challenges, and contributions as follows.
Modern automotive manufacturing networks are complex and global, comprising tens of thousands of parts and thousands of plants and suppliers. Such interconnection leaves the network vulnerable to disruptive events. A good risk mitigation decision support system should be data-driven, interpretable, and computational efficient. We devise such a tool via a linear optimization model, and integrate the model into the native information technology system at Ford Motor Company. In public security, policymakers face decisions regarding the placement of medical resources and training of healthcare personnel, to minimize the social and economic impact of potential large scale bio-terrorism attacks. Such decisions have to integrate the strategic positioning of medical inventories, understanding of adversary's behavior, and operational decisions that involve the deployment and dispensing of medicines.
We formulate a dynamic robust optimization model that addresses this decision question, apply a tractable solution heuristic, and prove theoretical guarantees of the heuristic's performance. Our model is calibrated with publicly available data to generate insights on how the policymakers should balance investment between medical inventory and personnel training. The World Health Organization and regional public health authorities decide on the influenza (flu) vaccine type ahead of flu season every year. Vaccine effectiveness has been limited by the long lead time of vaccine production - during the production period, flu viruses may evolve and vaccines may become less effective. New vaccine technologies, with much shorter production lead times, have gone through clinical trials in recent years. We analyze the question of optimal vaccine selection under both fast and slow production technologies. We formulate the problem as a dynamic distributionally robust optimization model.
Exploiting the network structure and using tools from discrete convex analysis, we prove some structural properties, which leads to informative comparative statics and tractable solution methods. With publicly available data, we quantify the societal benefit of current and future vaccine production technologies. We also explore the reduction in disease burden if WHO expand vaccine portfolio to include more than one vaccine strain per virus subtype. In each of the applications, our main contributions are four-fold. First, we develop mathematical models that capture the decision process. Second, we provide computational technology that can efficiently process these models and generate solutions. Third, we develop theoretical tools that guarantee the performance of these computational technology. Last, we calibrate our models with real data to generate quantitative and implementable insights.
by Peter Yun Zhang.
Ph. D. in Engineering Systems
Ph.D.inEngineeringSystems Massachusetts Institute of Technology, School of Engineering, Institute for Data, Systems, and Society

5G-and-beyond and Internet of Things (IoT) technologies are pushing a shift from the classic cloud-centric view of the network to a new edge-centric vision. In such a perspective, the computation, communication and storage resources are moved closer to the user, to the benefit of network responsiveness/latency, and of an improved context-awareness, that is, the ability to tailor the network services to the live user's experience. However, these improvements do not come for free: edge networks are highly constrained, and do not match the resource abundance of their cloud counterparts. In such a perspective, the proper management of the few available resources is of crucial importance to improve the network performance in terms of responsiveness, throughput, and power consumption. However, networks in the so-called Age of Big Data result from the dynamic interactions of massive amounts of heterogeneous devices. As a consequence, traditional model-based Resource Allocation algorithms fail to cope with this dynamic and complex networks, and are being replaced by more flexible AI-based techniques as a result. In such a way, it is possible to design intelligent resource allocation frameworks, able to quickly adapt to the everchanging dynamics of the network edge, and to best exploit the few available resources. Hence, Artificial Intelligence (AI), and, more specifically Machine Learning (ML) techniques, can clearly play a fundamental role in boosting and supporting resource allocation techniques at the edge. But can AI/ML benefit from optimal Resource Allocation? Recently, the evolution towards Distributed and Federated Learning approaches, i.e. where the learning process takes place in parallel at several devices, has brought important advantages in terms of reduction of the computational load of the ML algorithms, in the amount of information transmitted by the network nodes, and in terms of privacy. However, the scarceness of energy, processing, and, possibly, communication resources at the edge, especially in the IoT case, calls for proper resource management frameworks. In such a view, the available resources should be assigned to reduce the learning time, while also keeping an eye on the energy consumption of the network nodes. According to this perspective, a two-fold paradigm can emerge at the network edge, where AI can boost the performance of Resource Allocation, and, vice versa, optimal Resource Allocation techniques can speed up the learning process of AI algorithms. Part I of this work of thesis explores the first topic, i.e. the usage of AI to support Resource Allocation at the edge, with a specific focus on two use-cases, namely UAV-assisted cellular networks, and vehicular networks. Part II deals instead with the topic of Resource Allocation for AI, and, specifically, with the case of the integration between Federated Learning techniques and the LoRa LPWAN protocol. The designed integration framework has been validated on both simulation environments, and, most importantly, on the Colosseum platform, the biggest channel emulator in the world.

Allocating resources for applications is attributed to cost-efficiency measures only in the light of two other factors of paramount importance, namely application performance achieved and resource efficiency associated. Achieving satisfactory performance within QoS requirements is indeed the foremost objective to attain for any given application. However, the efficiency obtained for the relevant deployed resources is equally critical as it determines to what extent a resource allocation decision was comparable to optimality, and hence may be perceived cost-efficient in that regard. Achieving high application performance comes in conflict with maintaining high resource efficiency. The compromise between the two to seek a feasible trade-off at which a cost-efficient allocation can be claimed is without doubt a complex multi-dimensional problem as it directly has to deal with an adamant prime issue that is known as performance unpredictability. It is particularly raised in resource provisioning from large-scale clouds (whose infrastructure is virtualised and shared) due to factors mainly include: heterogeneity of cloud resources, workload uncertainty, and performance interference. This thesis attempts to optimise allocation decisions made for cloud-hosted applications against the challenge of performance unpredictability by improving their resource efficiency while ensuring that each application can satisfy its performance objectives in a cost-efficient deployment. To this end, we follow a holistic approach to present our contributions through which we address each factor of the aforementioned challenge when designing allocation mechanisms to achieve optimal allocations that are efficient performance-, utilisation-, and cost-wise. Firstly, we devise a resource allocation framework that exploits and thus benefits from heterogeneity of cloud resources such that application performance is predictable despite of being running on heterogeneous resources with varying computing capacities. Then, we address the long-standing problem of resource over-provisioning in cloud datacenters in response to workload uncertainty. Finally, we design and built a QoS-aware resource controlling system that enables coordinated execution amongst multiple applications on shared resources, with which a potential performance interference can be mitigated.

Thesis (Ph. D.) -- University of Maryland, College Park, 2005.
Thesis research directed by: Economics. Title from t.p. of PDF. Includes bibliographical references. Published by UMI Dissertation Services, Ann Arbor, Mich. Also available in paper.

Throughout the process industry, the conservation and allocation of mass and energy resources plays a pivotal role in the site wide optimization of a plant. Typically, raw materials are transformed into products, byproducts and wastes through pathways involving heating/cooling, pressure changes, mixing, reactions and separations. These pathways often require the addition or removal of energy from the system. The optimal management of such a system therefore requires conserving resources through the appropriate allocation of materials and energy. In a typical plant, there are both mass and energy objectives that require optimization. This dissertation will focus on optimizing the mass and energy resources present in a utility system. This will entail developing a novel framework of techniques to: target and design steam cogeneration networks while minimizing fuel requirements, identifying and utilizing sources of waste heat and incorporating heat pipes to enhance heat exchange networks. Additionally, a specific case of waste recovery will be examined when properties are the primary concern.

Much work has been done in simulating traditional cellular networks. But with the incoming of ad-hoc network technology, the next generation networks will employ hybrid network architectures using both cellular and ad-hoc networking concepts.

We investigate how to create a simulator being able to simulate a hybrid wireless network. This involves setting up a cellular network and an ad-hoc network respectively. However, the most important thing is how to integrate them seamlessly.

Fortunately, there has already been a simulator called SIMRA which simulates a UMTS cellular network. Therefore, this thesis work is greatly simplified as how to extend and improve SIMRA to implement a simulator for hybrid wireless network. We selected J-sim as the developing platform for our simulator and our development was greatly based on the wireless package provided by the latest version of J-sim.

To evaluate the new simulator, different resource allocation algorithms were run against it and the results were compared to those generated by earlier extensions to SIMRA under the same simulation settings. It showed that the resource allocation algorithms behaved similarly under the hybrid wireless network environment. Nevertheless, there are some discrepancies in behaviors of algorithms used for evaluation that still need to be studied.

The need for wireless communications has increased during the last decades. To increase the data rates of the communication links there is a need of allocating larger frequency bands. These bands are strictly regulated and the majority of the frequencies are allocated to licensed systems. The splitting of the bandwidth is orthogonal, which mean that the different systems are not interfering each other. But, orthogonal splitting is inefficient since it does not exploit all degrees of freedom in the wireless channels.

There are also unlicensed bands where different systems co-exist and operate simultaneously in a non-orthogonal manner and interfere each other. This interference degrades the performance of each system. This motivates the use of so-called spectrum sharing techniques for interference management.

The spectrum sharing can be modeled via the so-called interference channel (IFC). This consists of at least two transmitter (TX)-receiver (RX) pairs. These pairs can share resources such as frequency, time, power, code, or space. Here, the focus is on the sharing of spatial resources. By employing multiple antennas at the TXs, spatial diversity is obtained and it is possible to steer the power in any spatial direction. Assuming a single antenna at each RX we get the so-called multiple-input single-output (MISO) IFC.

There is a conflict inherent in the IFC since the TX-RX pairs optimize conflicting objectives, e.g., the data rates. To analyze this conflict we use game-theoretic concepts. In general, the situation where the TXs transmit in the directions which are optimal for their objective is inefficient. That is, it is possible increase all rates of some (or all) TX-RX pairs without decreasing the rate of any of the pairs. To do so, the TXs change their strategies such that interference is decreased.

We define several rate regions, which depend on the channel model and channelstate information at the transmitters. Also, some of the most important game-theoretic operating points are described.

This thesis includes three self-contained projects: In the first project Bidding strategies and their impact on the auctioneer's revenue in combinatorial auctions, focusing on combinatorial auctions, we propose a simple and efficient model for evaluating the value of any bundle given limited information, design bidding strategies that efficiently select desirable bundles, and evaluate the performance of different bundling strategies under various market settings. In the second project Retailer shelf-space management with promotion effects, promotional investment effects are integrated with retail store assortment decisions and shelf space allocation. An optimization model for the category shelf-space allocation incorporating promotion effects is presented. Based on the proposed model, a category shelf space allocation framework with trade allowances is presented where a multi-player Retailer Stackelberg game is introduced to model the interactions between retailer and manufacturers. In the third project Supply-chain oriented robust parameter design, we introduce the game theoretical method, commonly used in supply-chain analysis to solve potential conflicts between manufacturers at various stages. These manufacturing chain partners collaboratively decide parameter design settings of the controllable factors to make the product less sensitive to process variations.