Spelling suggestions: "subject:"ressourcenzuweisung"" "subject:"ressourcenzuteilung""
1 |
Multi-objective scheduling for real-time data warehousesThiele, Maik, Bader, Andreas, Lehner, Wolfgang 19 January 2023 (has links)
The issue of write-read contention is one of the most prevalent problems when deploying real-time data warehouses. With increasing load, updates are increasingly delayed and previously fast queries tend to be slowed down considerably. However, depending on the user requirements, we can improve the response time or the data quality by scheduling the queries and updates appropriately. If both criteria are to be considered simultaneously, we are faced with a so-called multi-objective optimization problem. We transformed this problem into a knapsack problem with additional inequalities and solved it efficiently. Based on our solution, we developed a scheduling approach that provides the optimal schedule with regard to the user requirements at any given point in time. We evaluated our scheduling in an extensive experimental study, where we compared our approach with the respective optimal schedule policies of each single optimization objective.
|
2 |
Partition-based workload scheduling in living data warehouse environmentsThiele, Maik, Fischer, Ulrike, Lehner, Wolfgang 04 July 2023 (has links)
The demand for so-called living or real-time data warehouses is increasing in many application areas such as manufacturing, event monitoring and telecommunications. In these fields, users normally expect short response times for their queries and high freshness for the requested data. However, meeting these fundamental requirements is challenging due to the high loads and the continuous flow of write-only updates and read-only queries that might be in conflict with each other. Therefore, we present the concept of workload balancing by election (WINE), which allows users to express their individual demands on the quality of service and the quality of data, respectively. WINE exploits these information to balance and prioritize both types of transactions—queries and updates—according to the varying user needs. A simulation study shows that our proposed algorithm outperforms competing baseline algorithms over the entire spectrum of workloads and user requirements.
|
3 |
Resource Allocation for Multiple-Input and Multiple-Output Interference NetworksCao, Pan 11 March 2015 (has links) (PDF)
To meet the exponentially increasing traffic data driven by the rapidly growing mobile subscriptions, both industry and academia are exploring the potential of a new genera- tion (5G) of wireless technologies. An important 5G goal is to achieve high data rate. Small cells with spectrum sharing and multiple-input multiple-output (MIMO) techniques are one of the most promising 5G technologies, since it enables to increase the aggregate data rate by improving the spectral efficiency, nodes density and transmission bandwidth, respectively. However, the increased interference in the densified networks will in return limit the achievable rate performance if not properly managed.
The considered setup can be modeled as MIMO interference networks, which can be classified into the K-user MIMO interference channel (IC) and the K-cell MIMO interfering broadcast channel/multiple access channel (MIMO-IBC/IMAC) according to the number of mobile stations (MSs) simultaneously served by each base station (BS). The thesis considers two physical layer (PHY) resource allocation problems that deal with the interference for both models: 1) Pareto boundary computation for the achiev- able rate region in a K-user single-stream MIMO IC and 2) grouping-based interference alignment (GIA) with optimized IA-Cell assignment in a MIMO-IMAC under limited feedback. In each problem, the thesis seeks to provide a deeper understanding of the system and novel mathematical results, along with supporting numerical examples. Some of the main contributions can be summarized as follows.
It is an open problem to compute the Pareto boundary of the achievable rate region for a K-user single-stream MIMO IC. The K-user single-stream MIMO IC models multiple transmitter-receiver pairs which operate over the same spectrum simultaneously. Each transmitter and each receiver is equipped with multiple antennas, and a single desired data stream is communicated in each transmitter-receiver link. The individual achievable rates of the K users form a K-dimensional achievable rate region. To find efficient operating points in the achievable rate region, the Pareto boundary computation problem, which can be formulated as a multi-objective optimization problem, needs to be solved. The thesis transforms the multi-objective optimization problem to two single-objective optimization problems–single constraint rate maximization problem and alternating rate profile optimization problem, based on the formulations of the ε-constraint optimization and the weighted Chebyshev optimization, respectively. The thesis proposes two alternating optimization algorithms to solve both single-objective optimization problems. The convergence of both algorithms is guaranteed. Also, a heuristic initialization scheme is provided for each algorithm to achieve a high-quality solution. By varying the weights in each single-objective optimization problem, numerical results show that both algorithms provide an inner bound very close to the Pareto boundary. Furthermore, the thesis also computes some key points exactly on the Pareto boundary in closed-form.
A framework for interference alignment (IA) under limited feedback is proposed for a MIMO-IMAC. The MIMO-IMAC well matches the uplink scenario in cellular system, where multiple cells share their spectrum and operate simultaneously. In each cell, a BS receives the desired signals from multiple MSs within its own cell and each BS and each MS is equipped with multi-antenna. By allowing the inter-cell coordination, the thesis develops a distributed IA framework under limited feedback from three aspects: the GIA, the IA-Cell assignment and dynamic feedback bit allocation (DBA), respec- tively. Firstly, the thesis provides a complete study along with some new improvements of the GIA, which enables to compute the exact IA precoders in closed-form, based on local channel state information at the receiver (CSIR). Secondly, the concept of IA-Cell assignment is introduced and its effect on the achievable rate and degrees of freedom (DoF) performance is analyzed. Two distributed matching approaches and one centralized assignment approach are proposed to find a good IA-Cell assignment in three scenrios with different backhaul overhead. Thirdly, under limited feedback, the thesis derives an upper bound of the residual interference to noise ratio (RINR), formulates and solves a corresponding DBA problem. Finally, numerical results show that the proposed GIA with optimized IA-Cell assignment and the DBA greatly outperforms the traditional GIA algorithm.
|
4 |
Resource Allocation for Multiple-Input and Multiple-Output Interference NetworksCao, Pan 12 January 2015 (has links)
To meet the exponentially increasing traffic data driven by the rapidly growing mobile subscriptions, both industry and academia are exploring the potential of a new genera- tion (5G) of wireless technologies. An important 5G goal is to achieve high data rate. Small cells with spectrum sharing and multiple-input multiple-output (MIMO) techniques are one of the most promising 5G technologies, since it enables to increase the aggregate data rate by improving the spectral efficiency, nodes density and transmission bandwidth, respectively. However, the increased interference in the densified networks will in return limit the achievable rate performance if not properly managed.
The considered setup can be modeled as MIMO interference networks, which can be classified into the K-user MIMO interference channel (IC) and the K-cell MIMO interfering broadcast channel/multiple access channel (MIMO-IBC/IMAC) according to the number of mobile stations (MSs) simultaneously served by each base station (BS). The thesis considers two physical layer (PHY) resource allocation problems that deal with the interference for both models: 1) Pareto boundary computation for the achiev- able rate region in a K-user single-stream MIMO IC and 2) grouping-based interference alignment (GIA) with optimized IA-Cell assignment in a MIMO-IMAC under limited feedback. In each problem, the thesis seeks to provide a deeper understanding of the system and novel mathematical results, along with supporting numerical examples. Some of the main contributions can be summarized as follows.
It is an open problem to compute the Pareto boundary of the achievable rate region for a K-user single-stream MIMO IC. The K-user single-stream MIMO IC models multiple transmitter-receiver pairs which operate over the same spectrum simultaneously. Each transmitter and each receiver is equipped with multiple antennas, and a single desired data stream is communicated in each transmitter-receiver link. The individual achievable rates of the K users form a K-dimensional achievable rate region. To find efficient operating points in the achievable rate region, the Pareto boundary computation problem, which can be formulated as a multi-objective optimization problem, needs to be solved. The thesis transforms the multi-objective optimization problem to two single-objective optimization problems–single constraint rate maximization problem and alternating rate profile optimization problem, based on the formulations of the ε-constraint optimization and the weighted Chebyshev optimization, respectively. The thesis proposes two alternating optimization algorithms to solve both single-objective optimization problems. The convergence of both algorithms is guaranteed. Also, a heuristic initialization scheme is provided for each algorithm to achieve a high-quality solution. By varying the weights in each single-objective optimization problem, numerical results show that both algorithms provide an inner bound very close to the Pareto boundary. Furthermore, the thesis also computes some key points exactly on the Pareto boundary in closed-form.
A framework for interference alignment (IA) under limited feedback is proposed for a MIMO-IMAC. The MIMO-IMAC well matches the uplink scenario in cellular system, where multiple cells share their spectrum and operate simultaneously. In each cell, a BS receives the desired signals from multiple MSs within its own cell and each BS and each MS is equipped with multi-antenna. By allowing the inter-cell coordination, the thesis develops a distributed IA framework under limited feedback from three aspects: the GIA, the IA-Cell assignment and dynamic feedback bit allocation (DBA), respec- tively. Firstly, the thesis provides a complete study along with some new improvements of the GIA, which enables to compute the exact IA precoders in closed-form, based on local channel state information at the receiver (CSIR). Secondly, the concept of IA-Cell assignment is introduced and its effect on the achievable rate and degrees of freedom (DoF) performance is analyzed. Two distributed matching approaches and one centralized assignment approach are proposed to find a good IA-Cell assignment in three scenrios with different backhaul overhead. Thirdly, under limited feedback, the thesis derives an upper bound of the residual interference to noise ratio (RINR), formulates and solves a corresponding DBA problem. Finally, numerical results show that the proposed GIA with optimized IA-Cell assignment and the DBA greatly outperforms the traditional GIA algorithm.
|
5 |
Online Resource Allocation in Dynamic Optical NetworksRomero Reyes, Ronald 13 May 2019 (has links)
Konventionelle, optische Transportnetze haben die Bereitstellung von High-Speed-Konnektivität in Form von langfristig installierten Verbindungen konstanter Bitrate ermöglicht. Die Einrichtungszeiten solcher Verbindungen liegen in der Größenordnung von Wochen, da in den meisten Fällen manuelle Eingriffe erforderlich sind. Nach der Installation bleiben die Verbindungen für Monate oder Jahre aktiv. Das Aufkommen von Grid Computing und Cloud-basierten Diensten bringt neue Anforderungen mit sich, die von heutigen optischen Transportnetzen nicht mehr erfüllt werden können. Dies begründet die Notwendigkeit einer Umstellung auf dynamische, optische Netze, welche die kurzfristige Bereitstellung von Bandbreite auf Nachfrage (Bandwidth on Demand - BoD) ermöglichen. Diese Netze müssen Verbindungen mit unterschiedlichen Bitratenanforderungen, mit zufälligen Ankunfts- und Haltezeiten und stringenten Einrichtungszeiten realisieren können. Grid Computing und Cloud-basierte Dienste führen in manchen Fällen zu Verbindungsanforderungen mit Haltezeiten im Bereich von Sekunden, wobei die Einrichtungszeiten im Extremfall in der Größenordnung von Millisekunden liegen können.
Bei optischen Netzen für BoD muss der Verbindungsaufbau und -abbau, sowie das Netzmanagement ohne manuelle Eingriffe vonstattengehen. Die dafür notwendigen Technologien sind Flex-Grid-Wellenlängenmultiplexing, rekonfigurierbare optische Add / Drop-Multiplexer (ROADMs) und bandbreitenvariable, abstimmbare Transponder. Weiterhin sind Online-Ressourcenzuweisungsmechanismen erforderlich, um für jede eintreffende Verbindungsanforderung abhängig vom aktuellen Netzzustand entscheiden zu können, ob diese akzeptiert werden kann und welche Netzressourcen hierfür reserviert werden. Dies bedeutet, dass die Ressourcenzuteilung als Online-Optimierungsproblem behandelt werden muss. Die Entscheidungen sollen so getroffen werden, dass auf lange Sicht ein vorgegebenes Optimierungsziel erreicht wird. Die Ressourcenzuweisung bei dynamischen optischen Netzen lässt sich in die Teilfunktionen Routing- und Spektrumszuteilung (RSA), Verbindungsannahmekontrolle (CAC) und Dienstgütesteuerung (GoS Control) untergliedern.
In dieser Dissertation wird das Problem der Online-Ressourcenzuteilung in dynamischen optischen Netzen behandelt. Es wird die Theorie der Markov-Entscheidungsprozesse (MDP) angewendet, um die Ressourcenzuweisung als Online-Optimierungsproblem zu formulieren. Die MDP-basierte Formulierung hat zwei Vorteile. Zum einen lassen sich verschiedene Optimierungszielfunktionen realisieren (z.B. die Minimierung der Blockierungswahrscheinlichkeiten oder die Maximierung der wirtschaftlichen Erlöse). Zum anderen lässt sich die Dienstgüte von Gruppen von Verbindungen mit spezifischen Verkehrsparametern gezielt beeinflussen (und damit eine gewisse GoS-Steuerung realisieren). Um das Optimierungsproblem zu lösen, wird in der Dissertation ein schnelles, adaptives und zustandsabhängiges Verfahren vorgestellt, dass im realen Netzbetrieb rekursiv ausgeführt wird und die Teilfunktionen RSA und CAC umfasst. Damit ist das Netz in der Lage, für jede eintreffende Verbindungsanforderung eine optimale Ressourcenzuweisung zu bestimmen. Weiterhin wird in der Dissertation die Implementierung des Verfahrens unter Verwendung eines 3-Way-Handshake-Protokolls für den Verbindungsaufbau betrachtet und ein analytisches Modell vorgestellt, um die Verbindungsaufbauzeit abzuschätzen. Die Arbeit wird abgerundet durch eine Bewertung der Investitionskosten (CAPEX) von dynamischen optischen Netzen. Es werden die wichtigsten Kostenfaktoren und die Beziehung zwischen den Kosten und der Performanz des Netzes analysiert. Die Leistungsfähigkeit aller in der Arbeit vorgeschlagenen Verfahren sowie die Genauigkeit des analytischen Modells zur Bestimmung der Verbindungsaufbauzeit wird durch umfangreiche Simulationen nachgewiesen. / Conventional optical transport networks have leveraged the provisioning of high-speed connectivity in the form of long-term installed, constant bit-rate connections. The setup times of such connections are in the order of weeks, given that in most cases manual installation is required. Once installed, connections remain active for months or years. The advent of grid computing and cloud-based services brings new connectivity requirements which cannot be met by the present-day optical transport network. This has raised awareness on the need for a changeover to dynamic optical networks that enable the provisioning of bandwidth on demand (BoD) in the optical domain. These networks will have to serve connections with different bit-rate requirements, with random interarrival times and durations, and with stringent setup latencies. Ongoing research has shown that grid computing and cloud-based services may in some cases request connections with holding times ranging from seconds to hours, and with setup latencies that must be in the order of milliseconds.
To provide BoD, dynamic optical networks must perform connection setup, maintenance and teardown without manual labour. For that, software-configurable networks are needed that are deployed with enough capacity to automatically establish connections. Recently, network architectures have been proposed for
that purpose that embrace flex-grid wavelength division multiplexing, reconfigurable optical add/drop multiplexers, and bandwidth variable and tunable transponders as the main technology drivers. To exploit the benefits of these technologies, online resource allocation methods are necessary to ensure that during network operation the installed capacity is efficiently assigned to connections. As connections may arrive and depart randomly, the traffic matrix is unknown, and hence, each connection request submitted to the network has to be processed independently. This implies that resource allocation must be tackled as an online optimization problem which for each connection request, depending on the network state, decides whether the request is admitted or rejected. If admitted, a further decision is made on which resources are assigned to the connection. The decisions are so calculated that, in the long-run, a desired performance objective is optimized. To achieve its goal, resource allocation implements control functions for routing and spectrum allocation (RSA), connection admission control (CAC), and grade of service (GoS) control.
In this dissertation we tackle the problem of online resource allocation in dynamic optical networks. For that, the theory of Markov decision processes (MDP) is applied to formulate resource allocation as an online optimization problem. An MDP-based formulation has two relevant advantages. First, the problem
can be solved to optimize an arbitrarily defined performance objective (e.g. minimization of blocking probability or maximization of economic revenue). Secondly, it can provide GoS control for groups of connections with different statistical properties. To solve the optimization problem, a fast, adaptive and
state-dependent online algorithm is proposed to calculate a resource allocation policy. The calculation is performed recursively during network operation, and uses algorithms for RSA and CAC. The resulting policy is a course of action that instructs the network how to process each connection request. Furthermore,
an implementation of the method is proposed that uses a 3-way handshake protocol for connection setup, and an analytical performance evaluation model is derived to estimate the connection setup latency. Our study is complemented by an evaluation of the capital expenditures of dynamic optical networks. The
main cost drivers are identified.
The performance of the methods proposed in this thesis, including the accuracy of the analytical evaluation of the connection setup latency, were evaluated by simulations. The contributions from the thesis provide a novel approach that meets the requirements envisioned for resource allocation in dynamic optical networks.
|
Page generated in 0.0393 seconds