비주기 메시지의 스케줄링 지연을 최소화하기 위한 TTCAN 스케줄링 알고리즘

Abstract

CAN(controller area network)은 1986년 자동차 산업을 위해 독일의 보쉬(Robert Bosch GmbH)에 의해 처음 개발되었다. CAN은 field-bus 방식의 차량용 네트워크이고, 개발하게 된 동기는 차량 내부가 점점 전자화 됨에 따라 통신 수단이 필요하게 되었으며, 무수히 많은 배선 문제를 해결하기 위해서 개발되었다. 1993년 CAN은 ISO-11898(고속 어플리케이션)과 ISO-11519(저속 어플리케이션)으로 표준화 되었다. TTCAN은 이러한 CAN의 물리계층과 데이터 링크계층을 그대로 사용하면서 이벤트 트리거 방식을 보완하기 위해 고안된 기술이다. 속도와 토폴로지는 CAN과 동일하고 이벤트 트리거링과 타임 트리거링을 동시에 제공한다. 2004년도에 ISO 11898-4 표준으로 재정되어 현재는 CAN 표준의 일부로 사용되고 있다.

이벤트 트리거 방식의 CAN의 단점을 보완한 방식이 TTCAN(Time-Triggered Controller Area Network)이고, 미리 지정된 스케줄에 따라 메시지를 전송하여 CAN(Controller Area Network)에 비해 높은 예측성(predictability)과 결정성(deterministic behavior)을 제공할 수 있다. 이러한 특징으로 인해 TTCAN은 차량용 네트워크는 물론 의료 장비, 산업 자동화 시스템 등과 같이 실시간성이 요구되는 다양한 어플리케이션에 널리 사용되고 있다.

TTCAN을 실시간 통신 시스템에 적용하기 위해서는 시스템 행렬(system matrix)이라고 불리는 메시지 스케줄을 만드는 것이 중요한 이슈가 된다. 현재까지 알려진 대부분의 연구는 주기적인 메시지의 성능에만 집중해왔으며, 비주기적인 메시지는 상대적으로 간과되어 왔다. 그러나, 대부분의 실시간 어플리케이션은 주기적인 메시지와 비주기적인 메시지를 모두 포함하는 것이 일반적이며, TTCAN 또한 두 종류의 메시지를 모두 지원할 수 있도록 설계되었다. TTCAN의 시스템 행렬은 주기적인 메시지를 위한 배타 윈도우(exclusive window), 비주기적인 메시지를 위한 중재 윈도우(arbitration window)을 포함하여 주기적인 메시지의 실시간성을 보장함은 물론 비주기적인 메시지의 통신 지연(communication delay)을 효과적으로 줄이는 것을 가능하게 한다.

본 논문에서는 주어진 임의의 시스템 행렬에 대해 주기적인 메시지들을 재배치하여 비주기적인 메시지의 최악 스케줄링 지연(worst-case scheduling delay) 을 최소화하는 메시지 재배치 알고리즘을 제안하고, 실험을 통하여 RMS(rate monotonic scheduling)한 경우보다 23~41(%) 정도 비주기적인 메시지의 지연시간이 감소됨을 나타낸다.; Time-Triggered Controller Area Network is widely accepted as a viable solution for real-time communication systems such as in-vehicle communications. However, although TTCAN has been designed to support both periodic and sporadic real-time messages, previous studies mostly focused on providing deterministic real-time guarantees for periodic messages while barely addressing the performance issue of sporadic messages.

In this paper, we present an O (n2) scheduling algorithm that can minimize the maximum duration of exclusive windows occupied by periodic messages, thereby minimizing the worst-case scheduling delays experienced by sporadic messages.

This optimization method has an increase in the real-time performance by a well distribution of the arbitrating windows within the communication matrix. It is able to produce increased performance rather than the RMS(rate monotonic scheduling) by 23~41(%) in minimizing the worst-case scheduling delays.