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. / Time Sensitive Networking (TSN) är en standard som utökar Ethernet genom att lägga till deterministiska garantier till intern kommunikation. Standarden har börjat användas inom fält såsom moderna bilar vars nätverk blir allt mer komplexa. Ett problem med TSN är det NP-hard svåra problemet med att schemalägga nätverksflöden, processen i vilket scheman uträknas för att garantera att nätverksflöden som kräver realtidsgarantier får sina krav uppfyllda. Uppsatsens mål är att implementera två olika schemaläggningsalgoritmer. Evalueringstesterna mäter algoritmernas förmåga att finna möjliga scheman för olika mängder av nätverksflöden och hur lång tid det tar.Algoritmernas tillvägagångssätt för schemaläggning jämförs och bedöms därefter.Denna uppsats implementerar två olika algorithmer, en finkorning algorithm och en grovkornig algoritm. Namnen kommer från finkornigheten i algoritmernas schemaläggning. Den finkorniga algoritmen schemalägger med finkornighet och den grovkorniga algoritmen schemalägger med grovkornighet. Resultatet från testerna och evalueringen visar att när algoritmerna schemalägger samma flöden tar den grovkorniga algoritmen som värst 42 gånger mer tid att slutföra sina beräkningar. Slutsatsen är att finkorning schemaläggning är inte applicerbar då det tar för lång tid att utföra för en väldigt liten mängd flöden.
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:kau-94050 |
| Date | January 2023 |
| Creators | Svensson, Emanuel |
| Publisher | Karlstads universitet, Institutionen för matematik och datavetenskap (from 2013) |
| Source Sets | DiVA Archive at Upsalla University |
| Language | English |
| Detected Language | English |
| Type | Student thesis, info:eu-repo/semantics/bachelorThesis, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.003 seconds