Finished PhD Theses

Network Coding Strategies for Multi-Core Architectures

by Dr.-Ing. Simon Wunderlich, 2021
 

 

Abstract

Random Linear Network Coding (RLNC) is a new coding technique which can provide higher reliability and efficiency in wireless networks. Applying it on the fifth generation of cellular networks (5G) is now possible due to the softwarization approach ofthe 5G architecture. However, the complex computations necessary to encode and decode symbols in RLNC are limiting the achievable throughput and energy efficiency on todays mobile computers.

Most computers, phones, TVs, or network equipment nowadays come with multiple, possibly heteregoneous (i.e. slow low-power and fast high-power) processing cores. Previous multi core research focused on RLNC optimization for big data chunks which are useful for storage, however network operations tend to use smaller packets (e.g.Ethernet MTUs of 1500 byte) and code over smaller generations of packets. Also latency is an increasingly important performance aspect in the upcoming Tactile Internet, however latency has received only small attention in RLNC optimization so far. The primary research question of my thesis is therefore how to optimize throughput and delay of RLNC on todays most common computing architectures. By fully leveraging the resources of todays consumer electronics hardware, RLNC can be practically adopted in todays wireless systems with just a software update and improve the network efficiency and user experience.

I am generally following a constructive approach by introducing algorithms and methods, and then demonstrating their performance by benchmarking actual implementations on common consumer electronics hardware against the state of the art. Inspired by linear algebra parallelization methods used in high performance computers (HPC), I’ve developed a RLNC encoder/decoder which schedules matrix block tasks for multiple cores using a directed acyclic graph (DAG) based on data dependencies betweenthe tasks. A non-progressive variant works with pre-computed DAG schedules which can be re-used to push throughput even higher. I’ve also developed a progressive variant which can be used to minimize latency. Both variants are achieving higher throughput performance than the fastest currently known RLNC decoder, with up to three times the throughput for small generation size and short packets. Unlike previous approaches, they can utilize all cores also on heterogeneous architectures. The progressive decoder greatly reduces latency while allowing to keep a high throughput, reducing the latency up to a factor ten compared to the non-progressive variant.

Progressive decoders need special low-delay codes to release packets early instead of waiting for more dependent packets from the network. I’m introducing Caterpillar RLNC (CRLNC), a sliding window code using a fixed sliding window over a stream of packets. CRLNC can be implemented on top of a conventional generation based RLNC decoder. CRLNC combines the resilience against packet loss and fixed resource boundaries (number of computations and memory) of conventional generation based RLNC decoders with the low delay of an infinite sliding window decoder.

The DAG RLNC coders and the Caterpillar RLNC method together provide a powerful toolset to practically enable RLNC in 5G or other wireless systems while achieving high throughput and low delay as required by upcoming immersive and machine control applications.

High-Throughput Air-to-Ground Connectivity for Aircraft

by Dr.-Ing. Sandra Hoppe, 2021, available at tud.qucosa.de
 

 

Abstract

Permanent connectivity to the Internet has become the defacto standard in the second decade of the 21st century. However, on-board aircraft connectivity is still limited. While the number of airlines offering in-flight connectivity increases, the current performance is insufficient to satisfy several hundreds of passengers simultaneously. There are several options to connect aircraft to the ground, i.e. direct air-to-ground, satellites and relaying via air-to-air links. However, each single solution is insufficient. The direct air-to-ground coverage is limited to the continent and coastal regions, while the satellite links are limited in the minimum size of the spot beams and air-to-air links need to be combined with a link to the ground. Moreover, even if a direct air-to-ground or satellite link is available, the peak throughput offered on each link is rarely achieved, as the capacity needs to be shared with other aircraft flying in the same coverage area. The main challenge in achieving a high throughput per aircraft lies in the throughput allocation. All aircraft should receive a fair share of the available throughput. More specifically, as an aircraft contains a network itself, a weighted share according to the aircraft size should be provided. To address this problem, an integrated air-to-ground network, which is able to provide a high throughput to aircraft, is proposed here. Therefore, this work introduces a weighted-fair throughput allocation scheme to provide such a desired allocation. While various aspects of aircraft connectivity are studied in literature, this work is the first to address an integrated air-to-ground network to provide high-throughput connectivity to aircraft. This work models the problem of throughput allocation as a mixed integer linear program. Two throughput allocation schemes are proposed, a centralized optimal solution and a distributed heuristic solution. For the optimal solution, two different objectives are introduced, a max-min-based and a threshold-based objective. The optimal solution is utilized as a benchmark for the achievable throughput for small scenarios, while the heuristic solution offers a distributed approach and can process scenarios with a higher number of aircraft. Additionally, an option for weighted-fair throughput allocation is included. Hence, large aircraft obtain a larger share of the throughput than smaller ones. This leads to fair throughput allocation with respect to the size of the aircraft. To analyze the performance of throughput allocation in the air-to-ground network, this work introduces an air-to-ground network model. It models the network realistically, but independent from specific network implementations, such as 5G or WiFi. It is also adaptable to different scenarios. The aircraft network is studied based on captured flight traces. Extensive and representative parameter studies are conducted, including, among others, different link setups, geographic scenarios, aircraft capabilities, link distances and link capacities. The results show that the throughput can be distributed optimally during high-aircraft-density times using the optimal solution and close to optimal using the heuristic solution. The mean throughput during these times in the optimal reference scenario with low Earth orbit satellites is 20 Mbps via direct air-to-ground links and 4 Mbps via satellite links, which corresponds to 10.7% and 1.9% of the maximum link throughput, respectively. Nevertheless, during low-aircraft-density times, which are less challenging, the throughput can reach more than 200 Mbps. Therefore, the challenge is on providing a high throughput during high-aircraft-density times. In the larger central European scenario, using the heuristic scheme, a minimum of 22.9 Mbps, i.e. 3.2% of the maximum capacity, can be provided to all aircraft during high-aircraft-density times. Moreover, the critical parameters to obtain a high throughput are presented. For instance, this work shows that multi-hop air-to-air links are dispensable for aircraft within direct air-to-ground coverage. While the computation time of the optimal solution limits the number of aircraft in the scenario, larger scenarios can be studied using the heuristic scheme. The results using the weighted-fair throughput allocation show that the introduction of weights enables a user-fair throughput allocation instead of an aircraft-fair throughput allocation. As a conclusion, using the air-to-ground model and the two introduced throughput allocation schemes, the achievable weighted-fair throughput per aircraft and the respective link choices can be quantified.

Agile Mobile Edge Computing and Network-coded Cooperation in 5G

by Dr.-Ing. Roberto Torre Arranz, 2021, available at tud.qucosa.de
 
M.Sc. Roberto Torre
 

Abstract

The architecture of the network is undergoing a series of structural changes from the core network to the user to pave the way for 5G. New infrastructure elements are being massively deployed, thus making 5G more heterogeneous. This emerging paradigm, along with new services and handheld devices, creates a massive, highly mobile, heterogeneous environment with hard constraints in throughput, latency, resilience, and power consumption. This dissertation presents Agile MEC (AMEC), a shift in the concept of MEC to support user’s mobility with the rapid relocation of services; and Network-coded Cooperation (NCC), a new system for massive content distribution in cellular networks. In summary, AMEC provides a mobility framework that reliably reduces the latency and power consumption in the system, and NCC improves network throughput, network resilience, and power consumption by offloading cellular traffic to underlay networks.

Next Generation Header Compression

by Dr.-Ing. Máté Tömösközi, 2021, available at tud.qucosa.de
 

 

Abstract

Header compression is one of the technologies, which enables packet-switched computer networks to operate with higher efficiency even if the underlying physical link is limited. Since its inception, the compression was meant to improve dial-up Telnet connections, and has evolved into a complex multi-faceted compression library, which has been integrated into the third and fourth generation of cellular networks, among others. Beyond the promised benefit of decreased bandwidth usage, header compression has shown that it is capable of improving the quality of already existing services, such as real-time audio calls, and is a developing hot topic to this day, realising, for example, Internet Protocol (IP) version 6 support on resource constrained low-power devices.

However, header compression is ill equipped to handle the stringent requirements and challenges, which are posed by the coming fifth generation of wireless and cellular networks (5G) and its applications. Even though it can be considered as an already well developed area of computer networks that can compress protocol headers with unparalleled efficiency, header compression is still operating under some assumptions and restrictions that could deny its employment outside of cellular Voice over IP transmissions to certain degrees. Albeit some improvements in the latency domain could be achieved with its help, the application of header compression in both largely interconnected networks and very dynamic ones — such as the wireless mesh and vehicular networks — is not yet assured, as the topic, in this perspective, is still relatively new and unexplored.

The main goal of my theses is the presentation and evaluation of novel ideas, which support the application of header compression concepts for the future wireless use-cases, as it holds alluring benefits for the coming network generations, if applied correctly. The dissertation provides a detailed treatment of my contribution in the specific research areas of header compression and network coding, which encompass novel proposals for their enhancement in 5G uses, such as broadcastability and online optimisation, as well as their subsequent analysis from various perspectives, including the achievable compression gains, delay reduction, transmission efficiency, and energy consumption, to name a few. Besides the focus on enabling header compression in 5G, the development of traffic-agnostic and various network-coded compression concepts are also introduced to attain the benefits of both techniques at the same time, namely, reduced bandwidth usage and high reliability in latency sensitive heterogeneous and error prone mesh networks. The generalisation of compression is achieved by the employment of various machine learning concepts, which could approximate the compression characteristics of any packet-based communication flow, while network coding facilitates the exploitation of the low-latency benefits of error correcting codes in heavily interconnected wireless networks.

Opportunistic Routing with Network Coding in Powerline Communications

by Dr.-Ing. Ievgenii Tsokalo, 2017, available at tud.qucosa.de
 

 

Abstract

Opportunistic Routing (OR) can be used as an alternative to the legacy routing (LR) protocols in networks with a broadcast lossy channel and possibility of overhearing the signal. The power line medium creates such an environment. OR can better exploit the channel than LR because it allows the cooperation of all nodes that receive any data. With LR, only a chain of nodes is selected for communication. Other nodes drop the received information. We investigate OR for the one-source one-destination scenario with one traffic flow. First, we evaluate the upper bound on the achievable data rate and advocate the decentralized algorithm for its calculation. This knowledge is used in the design of Basic Routing Rules (BRR). They use the link quality metric that equals the upper bound on the achievable data rate between the given node and the destination. We call it the node priority. It considers the possibility of multi-path communication and the packet loss correlation. BRR allows achieving the optimal data rate pertaining to certain theoretical assumptions. The Extended BRR (BRR-E) are free of them. The major difference between BRR and BRR-E lie in the usage of Network Coding (NC) for prognosis of the feedback. In this way, the protocol overhead can be severely reduced. We also study the Automatic Repeat-reQuest (ARQ) mechanism that is applicable to OR. It differs to ARQ with LR in that each sender has several sinks and none of the sinks except destination require the full recovery of the original message. Using BRR-E, ARQ and other services like network initialization and link state control, we design the Advanced Network Coding based Opportunistic Routing protocol (ANChOR). With the analytic and simulation results we demonstrate the near optimum performance of NChOR. For the triangular topology, the achievable data rate is just 2% away from the theoretical maximum and it is up to 90% higher than it is possible to achieve with LR. Using the G.hn standard, we also show the full protocol stack simulation results (including IP/UDP and realistic channel model). In this simulation, we revealed that the gain of OR to LR can be even more increased by reducing the head-of-the-line problem in ARQ. Even considering the ANChOR overhead through additional headers and feedbacks, it outperforms the original G.hn setup in data rate up to 40% and in latency up to 60%.

Adaptive MAC-Layer Protocol Switching for Power Line Communications (PLC)

by Dr.-Ing. Stanislav Mudriievskyi, 2017, available at dr.hut-verlag.de
 

 

Abstract

The ongoing change from conventional electrical grids towards smart grids brings new use cases to communication technologies. These influence the selection of appropriate communication systems according to the requirements of smart grid applications. Power Line Communications (PLC) is the most native communication technology for the smart grid as it uses the same medium for energy and data transmission. In order to meet the requirements of smart grid application perfectly the corresponding PLC system should be adapted dynamically. In this thesis adaptation mechanisms at the Medium Access Control (MAC) layer are studied on the example of a G.hn PLC system.

At first, the Physical (PHY) layer of G.hn is studied. Its model is implemented in the network simulator 3 (ns-3) according to the standard. At the MAC layer two channel access schemes can be used: Time Division Multiple Access (TDMA) or Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA). The CSMA/CA access scheme has numerous variations. In this thesis an adaptive version of CSMA/CA from another PLC system is analyzed in detail and improved. For the TDMA scheme the equal slot assignment is selected. It is used for symmetric traffic in uplink. The assignment of slots for scenarios with downlink traffic and for special cases with repeaters are studied as well.

It is known that two MAC access schemes under consideration have their advantages and disadvantages depending on the traffic load. Therefore, in this thesis the Adaptive Layer Switching (ALS) mechanism is proposed, which switches the MAC layer from CSMA/CA to TDMA or vice versa. The switching occurs for the whole network.

The novel ALS algorithm is described and implemented in the discrete event simulator ns-3. The operation of the networks with and without repeaters under variation of offered traffic is investigated. Three realistic network topologies are used: a small size one without repeaters, a medium size with one repeater and a large size one with three repeaters. Those are studied with User Datagram Protocol (UDP) and Transmission Control Protocol (TCP) traffic in uplink and downlink directions. The influence of the impulsive noise is studied as well. Finally, the performance of CSMA/CA, TDMA, and ALS in terms of delay and throughput is evaluated.

Analytische Modellierung zur Systemdimensionierung von 4G WiMAX Mobilfunknetzen

by Dr.-Ing. Volker Richter, 2017, available at dr.hut-verlag.de
 

 

Abstract

Die zunehmende Verbreitung von Smartphones führt zu einem exponentiellen Wachstum des mobilen Datenverkehrs. Dies erfordert einen weiteren Ausbau der Mobilfunknetze der vierten Generation, wie WiMAX und LTE. Gleichzeitig zwingt der harte Wettbewerb die Netzbetreiber, Ausbau- und Betriebskosten deutlich zu reduzieren. Daher ist die mittlere Zellauslastung zu erhöhen und zur Gewährleistung der Dienstqualität QoS-Unterstützung einzuführen. Dies erfordert eine Weiterentwicklung der Planungswerkzeuge unter Einbeziehung von QoS-Einflüssen.

Die vorliegende Arbeit beschreibt analytische Modelle zur Systemdimensionierung des 4G-Mobilfunknetzes WiMAX.

Der zu Grunde liegende IEEE 802.16-2012 Standard spezifiziert das Frameformat, die Nachrichten und das QoS-Konzept mit Verkehrsüberwachung und Scheduling. Konkrete Algorithmen werden allerdings nicht beschrieben.

Kein Ansatz zur Verkehrsüberwachung erfüllt die Forderung des Standards nach einer strikten zeitlichen Begrenzung des Integrationintervalls der Verkehrsmessung. Daher werden mit dem ACC und dem APP zwei eigene Algorithmen vorgestellt. Die Leistungsbewertung zusammen mit einem existierenden Ansatz zeigt, dass nur der ACC die Anforderungen des Standards erfüllt.

Mit dem TRBS wird ein QoS-unterstützender hybrider Scheduler vorgestellt. Nachrangig zu den QoS-Anforderungen erreicht dieser eine Gleichbehandlung der Teilnehmer, bezogen auf Funkressourcen. Im Gegensatz zu anderen Ansätzen unterscheidet der TRBS nicht zwischen Dienstklassen sondern zwischen garantierten und zulässigen Übertragungsanforderungen. Die Gegenüberstellung mit einem verbreiteten PF-Scheduler zeigt eine signifikante Leistungssteigerung, insbesondere für Echtzeit-Verbindungen.

Zur Entwicklung der analytischen Modelle wird zuerst der Einfluss des Frameformates und des Overheads unter idealen Kanalbedingungen untersucht. Die Modelle für garantierten und zulässigen Verkehr übertreffen mit einer Genauigkeit von 10^-3 bekannte Ansätze um den Faktor 10. Darüber hinaus wird mit Burst-Aggregation eine effizientere Variante des Downlink-Subframes modelliert.

Abschließend werden die analytischen Modelle um die Beschreibung realitätsnaher Kanalbedingungen erweitert. Unter diesen Bedingungen sinkt die Genauigkeit auf 10^-1 ab. Die vorgestellten analytischen Modelle können in kommerziellen Planungswerkzeugen zum Einsatz kommen und damit zu einem kosteneffizienteren Aufbau und Betrieb des 4G-Mobilfunknetzes WiMAX beitragen.

Energy-Efficient Indoor Localization Based on Wireless Sensor Networks

by Dr.-Ing. Jorge Juan Robles, 2015, available at dr.hut-verlag.de
 

 

Abstract

This thesis deals with the improvement of the performance of WSN-based localization systems. Particularly, our focus is to increase the energy efficiency of the battery powered nodes. For this, we investigate the main features in three areas of a localization system: the measurement process, the position estimation and the communication protocols.

Experiments were conducted to evaluate the accuracy of the Received Signal Strength Indicator (RSSI) and Phase of Arrival (POA) ranging methods. Based on the measurements, novel distance error models are derived for the POA ranging method.

The position accuracy of several localization algorithms are evaluated in different scenarios by using simulated and real data.

We designed a communication protocol called Highly Configurable Protocol (HCP), which is designed for RSSI-based localization systems. In this thesis we also present HCP version 2 (HCPv2), where the nodes can use both RSSI and POA measurements for the position estimation.