Implementation and evaluation of TSN scheduling algorithms

Abstract: Time Sensitive Networking (TSN) is a standard that extends Ethernet, providing deterministic guarantees to internal communications. The standard is finding use in many different fields such as modern cars whose networks are getting increasingly complex. One problem with TSN is the NP-hard problem of scheduling network flows, the process in which schedules are made to ensure that network flows demanding real-time guarantees have their requirements met.The goal of thesis is to implement two different scheduling algorithms. The evaluation of the implementations measure how they perform in regards to finding possible schedules and for how much time they take with an increasing number of network flows to schedule. The algorithms approaches to scheduling are then discussed and judged in comparison with the results. This thesis implements two different algorithms, a fine-grained algorithm and a coarse-grained algorithm. The difference between the algorithms lie in how fine-grained their scheduling is. Where the fine-grained algorithm adopts the lowest resolution permissible, the coarse-grained algorithm achieves the highest resolution possible in the schedule. The results show that the coarse-grained algorithm becomes unacceptably slow because of its fine-grained scheduling. In a scenario where algorithms 1 and 2 work with the same flows, the coarse-grained algorithm is 42x slower than the fine-grained algorithm in the worst case.The conclusion is that the finest possible scheduling is not a feasible approach because of it taking too much time to execute for a very small amount of flows.