(non-exhaustive list, click titles to expand)
Self Inspecting Python: A Framework for Automated Model Checking Applied to Automotive Software Testing
Degree: M.Sc.
Abstract: When a critical system stops working, it is mildly annoying at best and lives
are at stake at worst. The complexity and amount of critical systems in
cars has increased over the past years with car-to-x, accident avoidance, advanced driver-assistance, automated driving, remote diagnostics and many
more types of systems being introduced to them. It takes a lot of development and testing to ensure these systems are reliable and work alongside
each other without issue. This work explores model checking as a means to
ensure quality and correctness of software and software based testing, in order to improve the reliability of critical systems. It discusses how commonly
known issues with model checking can be addressed and explores the extent
to which model checking can be automated. In this regard, specifically model
creation and challenges in modelling Python code are investigated. Finally,
a novel approach to semi-automated model checking, ’soft model checking’,
is developed, demonstrated and analysed.
Theoretical and Practical Quantification of Network Calculus Analyses
Degree: M.Sc.
Abstract: Reliable performance guarantees are essential in
real-time communication systems, and network calculus offers
a formal framework to derive them. A key component of
this framework is the computation of output bounds, which
directly influence the tightness of delay and backlog estimates.
However, several methods exist for computing output bounds,
and their relative quality has not been thoroughly compared. This
thesis provides a systematic study of output bound computation
methods. We first analyze the approaches from a theoretical
perspective. By examining their mathematical definitions, we
establish formal proofs showing that some methods always yield
tighter results than others. This analysis enables us to discard
inferior approaches and focus on a smaller set of promising
candidates. We then complement the theoretical study with
an empirical evaluation for methods that can’t be ruled out
analytically. Using representative network models, we compare
the remaining methods in terms of tightness and initial burst.
The results provide a comparison that highlights trade-offs and
identifies the most effective methods for different application
contexts. In conclusion, this thesis clarifies the relationships between existing output bound methods and provides a structured
comparison of their strengths and weaknesses. These findings
offer a clearer basis for future work on refining output bound
computation within the framework of network calculus.
A Reinforcement Learning-Based Approach for Task Assignment in Automated Warehouses
Degree: M.Sc.
Abstract: Current manufacturing trends indicate a growing demand for highly customisable
production environments. The associated just-in-time manufacturing philosophy
increases the need for highly flexible supply chains and automated logistics processes. Warehouses, and particularly the picking of orders, play a crucial role
in supply chain productivity. For this reason, optimising the picking process is
a high priority. Automated guided vehicles (AGVs) are nowadays used to automate the picking process to a large extent. To make efficient use of these AGVs,
the multi-agent pickup and delivery (MAPD) optimisation problem must be addressed, involving the assignment of transport orders to vehicles and the planning
of conflict-free paths. Solutions to the MAPD problem either consider these subproblems jointly (coupled) or separately (decoupled). While coupled approaches
are more complex, decoupled approaches tend to be less optimal, requiring a trade-off between scalability and solution quality.
In light of the recent successes of reinforcement learning (RL) in the context of MAPD, this master’s thesis focuses on
investigating the potential of using RL to overcome the aforementioned trade-off.
To this end, a decoupled MAPD algorithm, called RTAW4A, has been developed.
RTAW4A is based on the architecture of the Aulis fleet management system and
uses RL to manage the assignment of transport orders. A comparison of the RL-based approach
with several well-known traditional decoupled MAPD algorithms
is presented within a developed simulation environment by means of an empirical
evaluation. The results show that using RL is advantageous in scenarios where
high traffic volumes cause significant delays in order execution. In such cases, the
developed approach calculates efficient task assignments quickly, even in scenarios
involving 1,000 AGVs. Conversely, the algorithm is susceptible to runtime issues in
scenarios where many tasks must be assigned simultaneously. This could possibly
be remedied by more intensive training. In terms of flexibility and reliability, the
evaluation of RTAW4A shows promising results for an application in automated
warehouses. Further investigations with RTAW4A are recommended to determine
its suitability for real-time applications.
Feed-forward Routing for the Application of Network Calculus Analyses
Degree: B.Sc.
Abstract: This thesis investigates algorithms for converting undirected network topologies into directed,
acyclic (feed-forward) networks to enable performance analysis with network calculus. Three
acyclic routing algorithms — Spanning Tree Protocol (STP), Up/Down Routing, Turn Prohibi-
tion (TP) — are compared, along with two path routing algorithms: shortest path and greedy
routing. Extensive simulations show that TP consistently allows greater resource utilization and
higher throughput compared to STP and Up/Down Routing, especially when paired with greedy
routing, which further reduces delay bounds. The study also adapts TP for weighted networks,
demonstrating that the optimal routing strategy depends on network size, degree, and link
weight distribution. Overall, combining TP with greedy routing offers significant improvements
for feed-forward routing in network calculus analyses.
Round Robin Scheduling Algorithms in Network Calculus: Modeling and Implementation
Degree: B.Sc.
Abstract: Providing worst-case guarantees is a common problem in many applications. Network
calculus provides a framework for determining such bounds in communication networks.
Efforts have been done in previous years to implement network calculus operations
through efficient algorithms. For this work, the well-known round robin scheduling
algorithm is implemented in a not-yet published backend. The worst-case delay bound
for every data flow in a network of multiple servers is analyzed. A directed search
algorithm is implemented to find an optimal combination of parameters. The relation
between scheduler parameters and flow configurations is investigated.
Finding and Breaking Cyclic Dependencies between Data Flows in Random Networks
Degree: B.Sc.
Abstract: With the rising amount of devices and an ever-increasing amount of communication
between them, having properly organized networks becomes more and more relevant.
Reducing the complexity by removing cyclic dependencies in non-feedforward networks
and creating an equivalent feedforward network is crucial for some algorithms and their
ffciency.
Cyclic dependencies can lead to infinite loops, causing unpredictable behavior as packets or calls can always be sent in a cycle. Furthermore, they also result in a lack of analyticity for the network, making debugging much more diffcult. Most importantly, certain Network Calculus algorithms simply cannot be used. This bachelor thesis implements the Service Partitioning algorithm proposed by Zhou et al. and therefore contributes to the understanding on how to resolve cycles in a network while still considering the aspect of effciency.
The authors state that this algorithm is more effcient than previous methods, while it also does not create the need for additional hardware and while providing enhanced flexibility by allocating non-identical network resources to buffers. In this thesis, we present, discuss, and implement the aforementioned algorithm. Furthermore, application options and both advantages and disadvantages are highlighted. Additionally, possible options on how to improve the algorithm and its results are also brought up and investigated.
This bachelor thesis serves as an independent re-implementation in a simulated and fully randomized network environment. This way, we hope to obtain significantly more generalizable results.
Cyclic dependencies can lead to infinite loops, causing unpredictable behavior as packets or calls can always be sent in a cycle. Furthermore, they also result in a lack of analyticity for the network, making debugging much more diffcult. Most importantly, certain Network Calculus algorithms simply cannot be used. This bachelor thesis implements the Service Partitioning algorithm proposed by Zhou et al. and therefore contributes to the understanding on how to resolve cycles in a network while still considering the aspect of effciency.
The authors state that this algorithm is more effcient than previous methods, while it also does not create the need for additional hardware and while providing enhanced flexibility by allocating non-identical network resources to buffers. In this thesis, we present, discuss, and implement the aforementioned algorithm. Furthermore, application options and both advantages and disadvantages are highlighted. Additionally, possible options on how to improve the algorithm and its results are also brought up and investigated.
This bachelor thesis serves as an independent re-implementation in a simulated and fully randomized network environment. This way, we hope to obtain significantly more generalizable results.
Network Analysis with the Improved TFA Algorithm
Degree: B.Sc.
Abstract: This thesis focuses on examining the behavior and performance bounds of the
TFA++ algorithm in network performance analysis. We replicate and analyze the
results of the original algorithm from the paper by Mifdaoui et al. We propose an
enhanced version tailored for feedforward networks, incorporating a caching method
to improve analysis time. Our evaluation specifically covers unicast systems and
compares the runtime and delay bounds of TFA++ with TFA and SFA algorithms.
We analyze prebuilt test networks from the DNC NCorg tool and compare our results with those presented in the paper above. Moreover, we explore the influence of
link transmission capacity on delay bounds. This research contributes to enhancing
our understanding of the algorithm’s behavior and provides valuable insights for
optimizing network performance.
Blackbox Testing of Network Calculus Analyses
Degree: B.Sc.
Abstract: There are now several software tools that perform Network Calculus analyses. Some of them are freely accessible, actively maintained, and open source. The tool with the longest history is the NetworkCalculus.org DNC. There are also other, more specialized tools from researchers who have implemented their latest results independently. The scope and capabilities of the tools vary considerably. Furthermore, there are unfortunately no standard definitions of how an analysis with a specific name should be performed. Researchers at EPFL have written an interface called Saihu that can launch several tools, including the NCorg DNC.
Linear Optimization in the DNC Analyses: Impact of the Solver on the Performance
Degree: B.Sc.
Abstract: Deterministic Network Calculus (DNC) offers various analyses for calculating upper bounds on the end-to-end delay of a data flow in a given network. The complexity of deriving this bound increases with the complexity of the network being analyzed. Different data flows cross each other, meet in a queue, and wait for their forwarding. Dependencies develop between the flows in the network, which must be correctly considered.
In DNC, there are two main categories of analysis: algebraic analysis and optimization analysis. This paper deals with Unique Linear Program (ULP) analysis. This is a variant of optimization analysis implemented in the Deterministic Network Calculator (NCorg DNC Tool). ULP converts the dependencies in a network into a linear program, which must then be solved by an optimization tool. This paper specifically deals with the optimization tool CPLEX. The goal is initially to develop an alternative implementation of the ULP analysis that uses the CPLEX API. The next step is to answer the question of how the analysis runtime can be specifically reduced both by using the API and by various parameter configurations in CPLEX, thus potentially achieving performance gains.
In DNC, there are two main categories of analysis: algebraic analysis and optimization analysis. This paper deals with Unique Linear Program (ULP) analysis. This is a variant of optimization analysis implemented in the Deterministic Network Calculator (NCorg DNC Tool). ULP converts the dependencies in a network into a linear program, which must then be solved by an optimization tool. This paper specifically deals with the optimization tool CPLEX. The goal is initially to develop an alternative implementation of the ULP analysis that uses the CPLEX API. The next step is to answer the question of how the analysis runtime can be specifically reduced both by using the API and by various parameter configurations in CPLEX, thus potentially achieving performance gains.
On the impact of the network topology on communication, exemplified by decentralized path planning for unmanned transport vehicles
Degree: B.Sc.
Abstract: The use of decentralized system architectures for distributed systems in the form
of peer-to-peer networks has meanwhile become very relevant due to their scalability and flexibility. Especially for industry 4.0, these properties should lead to
an increasing use of decentralized decision making. One of these application areas
is path planning for automated guided vehicles to enable collision-free crossings
within a shared working area. Therefore, in decentralized decision making the
vehicles have to communicate with each other. To enable efficent communication
between the participants of the network, a suitable network topology must be
selected. In this bachelor thesis, an application scenario for decentralized path
planning is constructed. The communication is managed by the topologies of a
fully meshed network with a single-hop strategy and the tree topology MINHTON
with a multi-hop strategy. A simulation is created, which enables the implementation and investigation the different approches. The testdata generated with that
simulation is analysed within an empirical evaluation.
It turns out that the dissemination time of both topologies is dramatically increased when too many different
messages have to be sent at the same time. While this effect appears with a higher
probability for a low number of regular senders in the fully meshed network, in
MINHTON it is more likely to be observed with many regular senders. The deviating behaviours can be explained by the different communication strategies used
by the topologies. In this way, the evaluation results can help to identify a trend
in relation to various simulation parameters. This might be a support by choosing
a single-hop or multi-hop strategy for a given scenario.
A MILP Approach by Parts for a Scalable Analysis of FIFO Feedforward Networks
Degree: M.Sc.
Abstract: In this paper we will focus on reducing the computation time of the worst-case end-to-end delay of a flow in
a network, where the approach used to compute the worst-case delays is the Mathematical programing (MP)
approach. For the reduction of the computation time an algorithm is developed to dismantle the network to
smaller parts and computed the delay of the flows in each part and then combining the results to achieve the
desired delay bound. All this while having as small as possible of an effect on the tightness of the computed
delay bounds. Also, the model of the worst-case delay calculations will be modified to instead, deliver the
worse-case backlog of all the flows going through a specific node in a network, and this calculated backlog
will be combined with the algorithm developed, to test and see if using the worst-case backlog computation is
beneficial in decreasing the computation time without affecting the tightness of the delay bounds.
Improving the LUDB-FF Delay Bounds by Partial Crossflow Cutting
Degree: M.Sc.
Abstract: The present thesis addresses the problem of computing the LUDB end-to-end delay bounds for
non-nested tandems in FIFO networks using Network Calculus by optimizing the cutting
methodology since the existing one of STA was (excessively) performing unnecessary cuts of the
crossflows. We have proposed a new cutting technique based on flow-cuts rather than server-cuts
along with an innovative mechanism of sets’ building notably, the score-based selection and the
minimum selection. Furthermore, we have assessed their results which yielded to enhanced delay
bounds comparing to STA.
Optimized Node Position Determination in null-Balanced Trees for Peer-to-Peer Networks
Degree: B.Sc.
Abstract: Peer-to-peer networks enable distributed applications, for which several peers use their
own resources and which have a high horizontal scalability. An overlay can be used to
organize the peers in order to establish optimized connections that are independent of
the physical network. One variant for the construction of overlays are tree structures.
Those that guarantee a logarithmic runtime for search operations, taking into account
a balancing criterion, are looked further upon here.
This work deals with the optimization of network entries and exits for tree structures with a null-balance. The focus lies on the conceptualization of a position finding procedure to determine a suitable tree position. By a strict reduction of admissible positions, network entries and exits can be completed in logarithmic time. For this purpose, a complete balancing of the tree structure still compatible with the null-balance is used. The efficiency of the shown runtime of position finding for large networks is confirmed in the evaluation of performed network simulations.
This work deals with the optimization of network entries and exits for tree structures with a null-balance. The focus lies on the conceptualization of a position finding procedure to determine a suitable tree position. By a strict reduction of admissible positions, network entries and exits can be completed in logarithmic time. For this purpose, a complete balancing of the tree structure still compatible with the null-balance is used. The efficiency of the shown runtime of position finding for large networks is confirmed in the evaluation of performed network simulations.
Improving the Min-plus-algebraic Network Calculus Analysis for Delay Bounding in FIFO Networks by Numerical Approximation
Degree: M.Sc.
Abstract: The presented work discusses the problem of finding a delay bound in a given Feed-Forward Network with FIFO-Multiplexing Servers. We propose new search based techniques in this context to find a good approximation for this problem rather than going
for a full optimization as state-of-the-art techniques in this context already do.
Deterministic Network Calculus for Multicasting: A Numerical Comparison Between Explicit Intermediate Bounds and Multicast Feed-Forward Analysis
Degree: B.Sc.
Abstract: Nowadays networked systems have become widely spread.
Computer networks are not only important for businesses and entertainment, but also for specific safety-critical applications.
One important example of a special-purpose network for such safety-critical applications are the Avionics Full-Duplex Switched Ethernet (AFDX) networks, which have been patented by Airbus.
These networks require guarantees about their performance, and Deterministic Network Calculus (DNC) has been used to certificate them.
An important characteristic is that their data flows are defined as Virtual Links (VL), which can be multicast.
However, for a long time DNC was not able to properly analyse such flows.
This limitation was previously circumvented by making overly pessimistic assumptions about the demands of the flows in the network.
Although valid, this kind of analysis leads to over-provisioning of the network, that in turn means unnecessary increases in cost.
In this work, we discuss the two most performant DNC multicast analysis methods presented in the literature.
These are the Explicit Intermediate Bounds (EIB) and the Multicast Feed Forward Analysis (MFF).
We compare both algorithms to the Unicast Transformation (UT) technique to analyse multicast flows regarding the quality of the bounded delay.
We also compare both algorithms to each other, and offer a comparative analysis of their performances.