A virtualização de redes tem se tornado cada vez mais proeminente nos últimos anos. Tal técnica permite a criação de infraestruturas de rede que se adaptam a necessidades específicas de aplicações de rede distintas, além de dar suporte à instanciação de ambientes favoráveis para o desenvolvimento e avaliação de novas arquiteturas e protocolos. Apesar de esforços recentes (motivados principalmente pela busca de mecanismos para avaliar propostas relacionadas à Internet do Futuro) terem contribuído substancialmente para a materialização desse conceito, nenhum preocupou-se em conciliar alocação eficiente de recursos e satisfação de requisitos de segurança (e.g., confidencialidade). É importante ressaltar que, no contexto de redes virtuais, a proteção de infraestruturas de rede compartilhadas constitui condição fundamental para seu uso em larga escala. É de grande importância que o impacto negativo causado pelo aprovisionamento de segurança seja considerado no processo de mapeamento de redes virtuais, de forma a permitir o uso integral dos recursos físicos sem subestimar requisitos de capacidade. Portanto, nesta dissertação, são propostos um modelo ótimo e um al- goritmo heurístico para realizar o mapeamento de redes virtuais em substratos físicos que têm por objetivo otimizar a utilização de recursos físicos garantindo a satisfação de requisitos de segurança. Ambas as abordagens possuem uma modelagem precisa de custos adicionais associados a mecanismos de segurança usados para proteger re- des virtuais, e são capazes de atender requisições de redes virtuais de forma online. Além disso, são apresentados os resultados de um extensivo processo de avaliação realizado, incluindo uma comparação detalhada entre o modelo ótimo e o algoritmo heurístico. Os experimentos revelam que o modelo baseado em Programação Linear Inteira é capaz de alocar redes virtuais de forma ótima em substratos físicos com até cem roteadores, enquanto que o algoritmo heurístico é capaz de adaptar-se a infraestruturas maiores, provendo mapeamentos sub-ótimos em um curto espaço de tempo. / Network virtualization has become increasingly prominent in recent years. It enables the creation of network infrastructures that are specifically tailored to the needs of distinct network applications and supports the instantiation of favorable en- vironments for the development and evaluation of new architectures and protocols. Although recent efforts (motivated mainly by the search for mechanisms to eval- uate Future Internet proposals) have contributed substantially to materialize this concept, none of them has attempted to combine efficient resource mapping with ful- fillment of security requirements (e.g., confidentiality). It is important to note that, in the context of virtual networks, the protection of shared network infrastructures constitutes a fundamental condition to enable its use in large scale. Considering the negative impact of security provisions in the virtual network embedding process is of paramount importance in order to fully utilize physical re- sources without underestimating capacity requirements. Therefore, in this thesis we propose both an optimal model and a heuristic algorithm for embedding virtual networks on physical substrates that aim to optimize physical resource usage while meeting security requirements. Both approaches feature precise modeling of over- head costs of security mechanisms used to protect virtual networks, and are able to handle virtual network requests in an online manner. In addition, we present the results of an extensive evaluation we carried out, including a detailed comparison of both the optimal model and the heuristic algorithm. Our experiments show that the Integer Linear Programming (ILP) model is capable of optimally embedding virtual networks on physical infrastructures with up to a hundred routers, while the heuristic algorithm is capable of scaling to larger infrastructures, providing timely, sub-optimal mappings.

[pt] A indústria das comunicações tem passado nos últimos anos, mundialmente, por profundas transformações. A Internet é a responsável pela maior destas transformações. Com o advento da Internet, existe a necessidade de uma banda de transmissão maior para o tráfego de dados. Para resolver esse problema, surgiu o conceito de redes ópticas e a multiplexação no domínio do comprimento de onda. Entretanto, isso criou um outro problema: o roteamento dos pacotes. A maior parte das redes de comunicação hoje em dia, ainda possui muitos sinais eletrônicos, o que significa que os sinais ópticos precisam ser convertidos em elétricos para serem ampliados, regenerados ou roteados e, depois, reconvertidos para ópticos. Isso acaba gerando atrasos na transmissão dos sinais e um gargalo nas redes ópticas. Para minimizar este problema, vários algoritmos foram criados. Apegando-se a tais fatos, este estudo explora o tema para implementar um algoritmo de enumeração recursiva, que tem como objetivo alocação de comprimentos em redes ópticas, visando minimizar o custo total de transmissão. Esse algoritmo foi testado e comparado com o algoritmo de programação linear, que fornece a solução ótima. / [en] The communication industry was passing in lastest years by great transformations in world. Internet is the mainly responsable for that, because there is the necessity of a large band to data transmission. The optical networks concept and wavelength division multiplexing technology were arised in order to solve this problem. However, this created another problem: the packet routing. The major part of communications networks still has electronics signals. This means that the optical signals have to be converted into electrical signals to be amplified, regenerated and routed and later recovered into optical. This implies in a delay on the data transmission and creates a bottleneck in the optical networks. Some algorithms have been created to minimize this problem. This dissertation has tried to develop an algorithm to solve RWA (routing and wavelength assignment) problems, aiming at the minimum total cost to transmitt datas. This algorithm was tested and compared with the linear program algorithm that gives the optimal solution to RWA problem.

Optimization plays an important role in many methods routinely used in statistics, machine learning and data science. Often, implementations of these methods rely on highly specialized optimization algorithms, designed to be only applicable within a specific application. However, in many instances recent advances, in particular in the field of convex optimization, make it possible to conveniently and straightforwardly use modern solvers instead with the advantage of enabling broader usage scenarios and thus promoting reusability. This paper introduces the R Optimization Infrastructure which provides an extensible infrastructure to model linear, quadratic, conic and general nonlinear optimization problems in a consistent way. Furthermore, the infrastructure administers many different solvers, reformulations, problem collections and functions to read and write optimization problems in various formats. / Series: Research Report Series / Department of Statistics and Mathematics

Orientador: Alexandre César Rodrigues da Silva / Abstract: Research in the field of quantum circuits has increased as technology advances in the development of quantum computers. IBM offers access to quantum computers via the cloud service called IBM Q. However, these architectures have some restrictions regarding the types of quantum gates that can be realized. This work proposes a methodology for the mapping of quantum and reversible circuits to the architectures made available by the IBM Q project. The methodology consists in finding CNOT mappings using a set of defined qubits movements to satisfy the architectures constraints by adding as few gates as possible. In order to reduce the number of CNOT gates needing mapping, the permutation of the circuit can be changed. One alternative to find this permutation is trough exhaustive search. However, is not feasible as the number of qubit increases. To solve this problem, the permutation problem was formulated as an Integer Linear Programming problem. The mapping of quantum circuits realized with non-implementable gates and reversible Toffoli circuits to the IBM quantum architectures were proposed in this work as well. This was done by adapting the developed CNOT mappings along with the Integer Linear Programming formulation. The proposed methodology was evaluated by mapping quantum and reversible circuits to an IBM quantum architectures with 5 and 16 qubits. The results were compared with two algorithms that map quantum circuits to IBM architectures. The cost metric used in the evalua... (Complete abstract click electronic access below) / Resumo: Pesquisa no campo de circuitos quânticos tem alavancado conforme a tecnologia avança no desenvolvimento de computadores quânticos. Atualmente, a IBM oferece acesso a computadores quânticos através do serviço em nuvem chamado IBM Q. No entanto, essas arquiteturas têm algumas restrições com relação aos tipos de portas quânticas e qubits em que uma porta CNOT pode ser implementada. Neste trabalho foi proposta uma metodologia para o mapeamento de circuitos quânticos e reversíveis para as arquiteturas disponibilizadas pelo projeto IBM Q. A metodologia consiste em mapear as portas CNOT utilizando uma série de movimentos de qubits, mantendo a permutação do circuito inalterada. A fim de reduzir o número de portas CNOT não implementáveis, a permutação do circuito pode ser alterada. Uma alternativa para encontrar essa permutação é a busca exaustiva. No entanto, é inviável conforme o número de qubits aumenta. Para resolver este problema, o problema de permutação foi formulado como um problema de Programação Linear Inteira. Como a metodologia é facilmente adaptável, o mapeamento de circuitos quânticos utilizando portas quânticas não implementáveis e circuitos reversíveis Toffoli também foram propostas neste trabalho. A avaliação da metodologia proposta foi feita com a realização do mapeamento de circuitos quânticos e reversíveis para arquiteturas quânticas com 5 e 16 qubits. Os resultados foram comparados com dois algoritmos que mapeiam circuitos quânticos para arquiteturas IBM. A métric... (Resumo completo, clicar acesso eletrônico abaixo) / Doutor

Water provides the lifeblood of Utah's agricultural economy. It Is the subject of much controversy and litigation and yet most opinions on the subject are based on opinions and prejudice rather than upon the basis of sound scientific examination. This paper attempts to provide some of the economic information necessary for sound decisions in the development and use of Utah's water resources with respect to agriculture. Utah has been divided into ten drainage regions (hydrologic subregions) and the presently irrigated and potentially irrigable land according to land class was estimated for each county or portion of a county within each of the regions. Water use factors, crop rotation constraints, costs of production, yields, product prices, and costs of bringing new land into production were also estimated. These values were then used in the linear program demand model to estimate a normalized demand (marginal value product) curve for water to be used in agricultural production within each region. The available level of water was varied in each of the demand curves to estimate the relationship between the quantity of water and its economic value (a demand function).

Nutritional and Economic Analysis of Small-Scale Agriculture in Imbabura, Ecuador Intervention projects in the developing world normally aim to satisfy either the nutritional needs of a group, or advancing the economic stability, but not both. One of the many issues that may arise by narrowly focusing and creating an aid program is that although a group may be fed, they are not equipped to mitigate risks that will arise after project completion and thus continue or revert back to a malnourished state. A bridge is required to join the economic and nutritional programs to create aid interventions that are sustainable past the point of donor separation. This paper proposes the creation of a linear program model to assess the effectiveness and sustainability of such intervention programs. Investigating the effects of merging economic and nutrition interventions as pursued in this report required the first step to be the creation of economic information for a typical small-scale farm. The region of Cochas, Imbabura, Ecuador was selected as the study area in which data would be collected for a representative sample of production and living circumstances of a poor, rural, and small-scale farmer. A comprehensive set of estimated cost and return (enterprise) budgets for small-scale agricultural crops that could be grown by the representative farm family used in this analysis was developed. This was accomplished via data collected in rural Ecuador by Jake Erickson, a Master's student in the department of Applied Economics at Utah State University. Of the supervisory committee, daily interaction occurred with Dr. DeeVon Bailey, project supervisor, and Dr. Ruby Ward, linear program specialist, whom were crucial in project completion. Various scenarios of the linear program were run with variations to the selection of nutritional requirements, off-farm income, and allowing food purchases off the family farm. Each of these scenarios was pursued as they mimic circumstances in which families may struggle to exist within the developing world. The results of each run are compared across the set of results to help understand what assumptions need to exist to validate an intervention's approach to improving the standard of living or nutrition of the world's poor, rural, small-scale farmers. This model is a preliminary attempt at assessing the sustainability of merging common intervention approaches and it should be recognized that further development is needed to create a more encompassing model. Utilizing enterprise budgets, a linear programming model, and nutritional information, such as is done in this study, can help in planning rural development interventions as the income maximization and least-cost diet models are integrated into one within the resource and management constraints of the representative small-scale farm.

Power-performance efficiency has become a central focus that is challenging in heterogeneous processing platforms as the power constraints have to be established without hindering the high performance. In this dissertation, a framework for optimizing the power and performance of GPUs in the context of general-purpose computing in GPUs (GPGPU) is proposed. To optimize the leakage power of caches in GPUs, we dynamically switch the L1 and L2 caches into low power modes during periods of inactivity to reduce leakage power. The L1 cache can be put into a low-leakage (sleep) state when a processing unit is stalled due to no ready threads to be scheduled and the L2 can be put into sleep state during its idle period when there is no memory request. The sleep mode is state-retentive, which obviates the necessity to flush the caches after they are woken up, thereby, avoiding any performance degradation. Experimental results indicate that this technique can reduce the leakage power by 52% on average. Further, to improve performance, we redistribute the GPGPU workload across the computing units of the GPU during application execution. The fundamental idea is to monitor the workload on each multi-processing unit and redistribute it by having a portion of its unfinished threads executed in a neighboring multi-processing unit. Experimental results show this technique improves the performance of the GPGPU workload by 15.7%. Finally, to improve both performance and dynamic power of GPUs, we propose two dynamic frequency scaling (DFS) techniques implemented on CPU host threads, one of which is motivated by the significance of the pipeline stalls during GPGPU execution. It applies a feedback controlling algorithm, Proportional-Integral-Derivative (PID), to regulate the frequency of parallel processors and memory channels based on the occupancy of the memory buffering queues. The other technique targets on maximizing the average throughput of all parallel processors under the dynamic power constraints. We formalize this target as a linear programming problem and solve it on the runtime. According to the simulation results, the first technique achieves more than 22% power savings with a 4% improvement in performance and the second technique saves 11% power consumption with 9% performance improvement. The contributions of this dissertation represent a significant advancement in the quest for improving performance and reducing energy consumption of GPGPU.

在此論文中，我們提出一個用來解釋線性規劃問題的類神經網路系統。這 個系統，我們取名為 LP-ANN 系統，它引用了能量函數(Energy Function)的概念及懲罰(Penalty)的方法。從這兩個概念，我們提出了一 個處理非負限制式的新想法。基本上，這個 LP-ANN 系統是以數位電腦來 做模擬，而不以類比式的電子電路來做模擬。這個系統可以判斷所給的線 性規劃問題是否有最佳解。如果有的話，再進一步找出一個符合可接受準 確度範圍內的最佳解。最後，以1200個任意產生的線性規劃問題來測試系 統的模擬結果也在本篇論文中詳述。

The ongoing development of new and demanding Internet applications requires the Internet to deliver better service levels that are significantly better than the best effort service that the Internet currently provides and was built for. These improved service levels include guaranteed delays, jitter and bandwidth. Through extensive research into Quality of Service and Differentiated Service (DiffServ) it has become possible to provide guaranteed services, however this turns out to be inadequate without the application of Traffic Engineering methodologies and principles. Traffic Engineering is an integral part of network operation. Its major goal is to deliver the best performance from an existing service provider's network resources and, at the same time, to enhance a customers' view of network performance. In this thesis, several different traffic engineering methods for optimising the operation of native IP and IP networks employing MPLS are proposed. A feature of these new methods is their fast run times and this opens the way to making them suitable for application in an online traffic engineering environment. For native IP networks running shortest path based routing protocols, we show that an LP-based optimisation based on the well known multi-commodity flow problem can be effective in removing network congestion. Having realised that Internet service providers are now moving towards migrating their networks to the use of MPLS, we have also formulated optimisation methods to traffic engineer MPLS networks by selecting suitable routing paths and utilising the feature of explicit routing contained in MPLS. Although MPLS is capable of delivering traffic engineering across different classes of traffic, network operators still prefer to rely on the proven and simple IP based routing protocols for best effort traffic and only use MPLS to route traffic requiring special forwarding treatment. Based on this fact, we propose a method that optimises the routing patterns applicable to different classes of traffic based on their bandwidth requirements. A traffic engineering comparison study that evaluates the performance of a neural network-based method for MPLS networks and LP-based weight setting approach for shortest path based networks has been performed using a well-known open source network simulator, called ns2. The comparative evaluation is based upon the packet loss probability. The final chapter of the thesis describes the software development of a network management application called OptiFlow which integrates techniques described in earlier chapters including the LP-based weight setting optimisation methodology; it also uses traffic matrix estimation techniques that are required as input to the weight setting models that have been devised. The motivation for developing OptiFlow was to provide a prototype set of tools that meet the congestion management needs of networking industries (ISPs and telecommunications companies - telcos).

Development drilling is used in underground mining to create access tunnels. A common method involves using a drilling rig, known as a jumbo, to drill holes into the face of a tunnel. Jumbo drill rigs have two or more articulated arms with drills as end-effectors, that extend outwards from a vehicle. Once drilled, the holes are charged with explosives and fired to advance the tunnel. There is an ongoing imperative within the mining industry to reduce development times and reducing time spent drilling is seen as the best opportunity for achieving this. Notwithstanding that three-boom jumbos have been available for some years, the industry has maintained a preference for using jumbo rigs with two drilling booms. Three-boom machines have the potential to reduce drilling time by as much as one third, but they have proven difficult to operate and, in practice, this benefit has not been realized. The key difficulty lies in manoeuvering the booms within the tight confines of the tunnel and ensuring sequencing the drilling of holes so that each boom spends maximum time drilling. This thesis addresses the problem of optimally sequencing multi-boom jumbo drill rigs to minimize the overall time to drill a blast hole pattern, taking into account the various constraints on the problem including the geometric constraints restricting motion of the booms. The specific aims of the thesis are to: ² develop the algorithmic machinery needed to determine minimum- or near-minimum-time drill assignment for multi-boom jumbos which is suitable for "real-time" implementation; ² use this drill pattern assignment algorithm to quantify the benefits of optimal drill pattern assignment with three-boom jumbos; and ² investigate the management of unplanned events, such as boom breakdowns, and assess the potential of the algorithm to assist a human operator with the forward planning of drill-hole selection. Jumbo drill task assignment is a combinatorial optimization problem. A methodology based around receding horizon mixed integer programming is developed to solve the problem. At any time the set of drill-holes available to a boom is restricted by the location of the other booms as well as the tunnel perimeter. Importantly these constraints change as the problem evolves. The methodology builds these constraints into problem through use of a feasibility tensor that encodes the moves available to each boom given configurations of other booms. The feasibility tensor is constructed off-line using a rapidly exploring random tree algorithm. Simulations conducted using the sequencing algorithm predict, for a standard drill-hole pattern, a 10 - 22% reduction in drilling time with the three-boom rig relative to two-boom machines. The algorithms developed in this thesis have two intended applications. The first is for automated jumbo drill rigs where the capability to plan drilling sequences algorithmically is a prerequisite. Automated drill rigs are still some years from being a reality. The second, and more immediate application is in providing decision support for drill rig operators. It is envisaged that the algorithms described here might form the basis of a operator assist that provides guidance on which holes to drill next with each boom, adapting this plan as circumstances change.