Francisco Pozo försvarar sin licentiatuppsats i datavetenskap

Disputationer och licentiatseminarier

Datum: 2017-04-06
Tid: 14.00
Plats: Mälardalens högskola, sal Gamma, Västerås.

Francisco Pozo vid akademin för innovation, design och teknik (IDT) försvarar sin licentiatuppsats i datavetenskap den 6 april klockan 14.00 i Västerås.

Titel:Synthesis of Extremely Large Time-Triggered Network Schedules

Serienummer: 255.

Betygsnämnd är Zdenek Hanzalek, Czech Technical University, universitetslektor Radu Dobrin, MDH, professor Mikael Sjödin, MDH. Reserv är professor Björn Lisper, MDH.

Sammanfattning

Datornätverk som ger datorer möjlighet att utbyta information är ingen nyhet. Kraven på sådana nätverk förändras dock över tid. För bl.a. fordons- och flygtillämpningar räcker det inte med att informationen levereras, den måste dessutom levereras vid rätt tidpunkt. Som ett exempel måste en airbag i en bil aktiveras vid exakt rätt tidpunkt. Sker det för tidigt kommer airbagen att hinna tömmas innan den fyllt sin funktion vid en kollision. Sker det för sent kan den explodera i ansiktet på dem som färdas i fordonet, vilket kan leda till allvarliga personskador. Det är alltså viktigt att signalen levereras vid rätt tidpunkt; från den givare som detekterar krocken till styrenheten som aktiverar airbagen. Exemplet illustrerar vikten av timing i den kommunikation som sker över datornätverket i bilen.
Nätverk som kan tillhandahålla den här typen av garantier brukar kallas realtidsnätverk. De kännetecknas av att meddelanden som skickas har förutsägbara fördröjningar som ger garantier för leverans inom en förutbestämd tid. En etablerad metod för detta är tidstriggad kommunikation, d.v.s. att meddelandena skickas vid förutbestämda tider. Typiskt sker överföringen av ett visst meddelande periodiskt, exempelvis var tionde millisekund. Såväl tidpunkter som periodtid bestäms innan systemet tas i drift genom att ett (så kallat) statiskt schema genereras utifrån de krav som gäller för kommunikationen. Vid drift sker sedan kommunikationen i enlighet med detta schema. Det hela liknar tidtabeller för tågtrafik, med tåg som tar sig från A till B via ett antal mellanliggande stationer i enlighet med de tider som finns i tidtabellen. Givet att tidtabellen är korrekt konstruerad och att alla tåg följer tidtabellen så går det (åtminstone i princip) att med stor sannolikhet garantera att tågen kommer fram i tid.
Avhandlingen behandlar generering av statiska scheman (tidtabeller) för tidstriggad kommunikation i extremt stora datornätverk, kanske med över tusen datorer och milliontals olika meddelanden. Det är inget enkelt problem. För att lösa det så delar vi upp problemet i ett antal enklare delproblem som kan lösas separat. Lösningarna för de olika delproblemen kombineras sedan till en lösning för hela problemet. Om vi exempelvis behöver generera ett schema som är 1 timme långt skulle detta kunna delas upp i 60 segment på vardera 1 minut, som enskilt är relativt enkla att schemalägga. Konkret sker schemaläggningen genom att problemet översätts till ett antal matematiska ekvationer som sedan löses med existerande metoder. I detta fall används en så kallad SMT-lösare för att härleda tidpunkterna för när meddelanden ska överföras i nätverket. När schemaläggningen på detta sätt gjorts för samtliga segment kan segmenten kombineras och bildar därmed det kompletta schemat.
Vi har utvärderat vår metod för generering av scheman för ett stort antal scenarier. Resultaten visar tydligt att metoden klarar av att generera scheman för system av önskvärd komplexitet, något som tidigare metoder inte klarade av.