Controller area network response time analysis and scheduling for advanced topics: Offsets, FIFO queues and gateways

Abstract

DAA elektronik kontrol üniteleri (EKÜ) arasındaki haberleşme en yaygın olarak kullanılanaraç içi haberleşme ağıdır. DAA'in öncelik tabanlı bir tahkim mekanizması vardır ve klasik kullanımda EKÜ'ler üzerinde öncelik kuyrukları kullanıldığı varsayılır. Bu varsayıma dayanarak, literatürde en kötü durum tepki süreleri hesaplamaları ve mesajların gerçek zamanlı zaman sınırlarını karşılayan uygun öncelik atamaları için etkili algoritmalar bulunmaktadır.Aktüel DAA ağlarında klasik duruma ek olarak başka durumlar vardır. Birincisi, araçlarayeni özelliklerin eklenmesi, mevcut DAA ağlarına uygun öncelikleri ile yeni mesajlarıneklenmesini gerektirir. İkincisi, FIFO kuyrukları çeşitli nedenlerden dolayıöncelik kuyruklarının yerine kullanılabilir. Üçüncü olarak, sürekli artan veri yoğunluğundan dolayı DAA ağları, ağ geçitleriyle mesajlar arasındaki çekişmeyi azaltmakiçin çeşitli kısımlara ayrılmıştır. Dördüncü olarak diğer bir önlem mesajlara görecelikonumlar atayarak mesaj iletimini zamana yaymaktır. Belirtilen tüm bu ek özelliklertepki süresi hesaplamaları ve öncelik atamaları için yeni metotları gerektirir.Bu tez yukarıda listelenen DAA ileri konuları için yapılan katkıları bir liste olaraksunmaktadır. Göreceli konum çizelgelemesi için, göreceli konum ve öncelik değerleribelirlenmiş mesaj setleri için farklı çizelgeleme analiz yöntemleri daha öncekigöreceli konum atama algoritmalarıyla birleştirilmiştir. Sonra, aynı anda öncelik vegöreceli konum ataması yapabilen yeni bir algoritma önerilmektedir. FIFO kuyruğukullanan EKÜ'ler için, daha önceki çizelgeleme analiz yöntemi geliştirilmiş ve bualgoritmanın çalışma süresi düşürülmüştür. Daha sonra bu algoritma var olan bir mesajsetine ekleme yapabilmek için öncelik atayabilecek hale getirilmiştir. Ağ geçitleriiçin, öncelik kuyruğu kullanan EKÜ'lere yönelik öncelik atama algoritması önerilmişve halihazırdaki çizelgeleme analizi FIFO kuyrukları da kapsayacak şekilde geliştirilmiştir.Bu tezde kullanılan ve geliştirilen tüm algoritmalar C++'da yazılmış ve yeni bir araçiçi ağ analiz ve tasarım aracı olan AUTONET'e entegre edilmiştir.

Controller Area Network (CAN) is the most widely used in-vehicle network for thecommunication among electronic control units (ECUs). CAN has a priority-basedarbitration mechanism and the classical usage of CAN assumes the implementationof priority queues (PQs) on ECUs. Based on this assumption, the literature providesefficient algorithms for the computation of worst-case response times (WCRTs) ofmessages as well as for the appropriate assignment of priorities to messages in orderto meet real-time guarantees such as message deadlines.In contemporary CAN networks there are several extensions to the classical case.First, the addition of new functionality to vehicles requires adding new messageswith appropriate priorities to existing CAN networks. Second, FIFO queues (FQs)might be used instead of PQs for easier implementation. Third, due to the everincreasingbus load, CAN networks are usually divided into several segments that areconnected via gateways to decrease the contention among messages. Fourth, a furthermeasure is to distribute the message transmission of each ECU over time by assigningtransmission offsets to messages. All of the stated extensions require new methodsfor WCRT analysis and priority assignment on CAN.This thesis has a list of contributions that address the extensions for CAN as listedabove. Regarding offset scheduling; different schedulability analysis methods formessage sets with given offset and priority assignments are incorporated to a previousoffset assignment algorithm. Then, a new algorithm which simultaneously assignsthe message offsets and priorities is proposed. Regarding ECUs with FIFO queues;the previous schedulability analysis is improved to decrease its run time and thenthis analysis is used in an algorithm that assigns the priorities to the new messagesthat extend an existing CAN network. Regarding gateways; an algorithmic priorityassignment is proposed for ECUs with priority queues and the schedulability analysisfor CAN networks with gateways is extended to FIFO queues.All of the algorithms that are used and developed in this thesis are implemented inC++ to integrate into a novel in-vehicle network analysis and design tool; AUTONET.