# Controller Area Network / CAN 的基礎介紹

- 支援 Multicast 跟 Broadcast
- Multicast 是人人都可以是某個 message 的發送者
- Broadcast 是人人都可以接收到一個 message
- 低成本
- 「競爭 Contention」的時候有「決定性 Deterministic」的解
- 白話來說就是競爭優先權時可以明確知道誰一定是贏家
- 因為如果是其他常見的協議，例如 WiFi 的 CSMA-CA，發生競爭時是等待「隨機的時間」，因此不能確定誰一定會拿到頻段的使用權
- 基於「優先權」的「仲裁/arbitration」
- 決定誰可以先使用電線來傳 message 的時候是依據「優先權」
- 除了用於汽車，也用於自動化、工控、航空、醫療等等設備上
- 只需要兩條電線
- 速率上看 1Mbps
- 錯誤檢測跟 signaling

## 使用原因

因為 CAN 的以下特點，使得 CAN 歷久不衰

- 便宜且簡單(只要兩條電線)
- Deterministic 且 upper bound 有保障(基於優先權)
- 用了很久依舊可以用

雖然有人享用其他協議(例如 Ethernet)來取代 CAN，但是大多都有成本問題，因此頂多互相競爭，目前不會到取代的程度。

## 更多資訊

- CAN 可以算是 MAC 層
- 也就是主要描述訊息如何進行傳遞
- CAN 不需要 node (或 system) configuration information
- configuration information 例如像「地址」，許多協議會需要知道發送人的「地址」，也就是發送人是誰
- 但是 CAN 不需要，他只要基於優先權作判斷就好
- 也因此具有 Flexibility，想在哪裡加入 node/ECU，就在那裡加入
- Message delivery Multicast Data consistency

# Frame Types

下面介紹 CAN 的 Data Frame 裡面有哪些部分。

CAN Frame 跟 Frame 之間會有 3 個 bit 的 inter-frame spacing。

## Base Data Frame

下面是 Base Data Frame。

| Field name | Length (Bits) | Purpose |
|:---------------------------------:|:-------------:|:--------------------------------------------------------------------------------:|
| Start-of-frame | 1 | Denotes the start of frame transmission |
| Identifier | 11 | A (unique) identifier which also represents the message priority |
| Remote transmission request (RTR) | 1 | Must be dominant (0) for data frames and recessive (1) for remote request frames |
| Identifier extension bit (IDE) | 1 | Must be dominant (0) for base frame format with 11-bit identifiers |
| Reserved bits (r0) | 1 | Reserved bit. Must be dominant (0), but accepted as either dominant or recessive |
| Data length code (DLC) | 4 | Number of bytes of data (0–8 bytes) |
| Data field | 0~64 | Data to be transmitted (length in bytes dictated by DLC field) |
| CRC | 15 | Cyclic redundancy check |
| CRC delimeter | 1 | Must be recessive (1) |
| ACK slot | 1 | Transmitter sends recessive (1) and any receiver can assert a dominant (0) |
| ACK delimeter | 1 | Must be recessive (1) |
| End-of-frame (EOF) | 7 | Must be recessive (1) |

## Extended Data Frame

Extended 的主要差別是在 Identifier 變成有 A 跟 B 兩部分，因為現在的 message 種類越來越多，11 bit 只有 2048 種，已經不夠用了，於是又多加了 18 bit 進去。

| Field name | Length (Bits) | Purpose |
|:---------------------------------:|:-------------:|:--------------------------------------------------------------------------------:|
| Start-of-frame | 1 | Denotes the start of frame transmission |
| Identifier A | 11 | First part of the (unique) identifier which also represents the message priority |
| Substitute remote request (SRR) | 1 | Must be recessive (1) |
| Identifier extension bit (IDE) | 1 | Must be recessive (1) for extended frame format with 29-bit identifiers |
| Identifier B | 18 | Second part of the (unique) identifier which also represents the message priority |
| Remote transmission request (RTR) | 1 | Must be dominant (0) for data frames and recessive (1) for remote request frames |
| Reserved bits (r1, r0) | 2 | Reserved bits which must be set dominant (0), but accepted as either dominant or recessive |
| Data length code (DLC) | 4 | Number of bytes of data (0–8 bytes) |
| Data field | 0~64 | Data to be transmitted (length in bytes dictated by DLC field) |
| CRC | 15 | Cyclic redundancy check |
| CRC delimeter | 1 | Must be recessive (1) |
| ACK slot | 1 | Transmitter sends recessive (1) and any receiver can assert a dominant (0) |
| ACK delimeter | 1 | Must be recessive (1) |
| End-of-frame (EOF) | 7 | Must be recessive (1) |

# Bit Stuffing

CAN 有規定，在傳輸的過程中，如果傳了連續 5 個相同的 bit，那麼下一個 bit 一定要傳一個相反的額外 bit。

例如在傳某個 message 時長得像 ...111111010...，連續傳了 5 個 1 的時候，下一個一定要傳 0，才接著繼續傳剩下的 1010。

會需要這個規定的原因是為了保留來判斷 EOF 。

:::warning
實際上在傳最後 10 個 bit 的 1 的時候就不會有 stuffing 了
:::

# Data Efficiency

在討論 protocol 的時候，一定會討論到的就是傳輸資料的效率，所以我們來看傳出去的 bits 中，究竟有多少比例是真正的資料。

:::info
下面討論的是 Base Data Frame。
:::

## 最長長度

- data field：64 bits
- 是指最多有 64 bits
- other fields：44 bits
- 可以自己去上面加加看
- inter-frame spacing：3 bits

接著考慮到 bit stuffing，來想最極端的情況會多補幾個 bit。

答案是 24 個 bits，最極端的情況就是 11111000011110000....，這種情況下可以發現上一個連續情形補的 bit，會成為下一個連續情形的一部分。

$$
\left\lfloor \frac{64+34-1}{4}\right\rfloor=24
$$

other field 只考慮了 34 bits 是因為最後的 10 個 1 不需要考慮 stuffing。

因此最長長度就是 64 + 44 + 3 + 24 = 135 bit

## 最佳效率

假設並沒有發生 bit stuffing，那麼比率就是：

$$
\frac{64}{64+44+3}=0.576...
$$

## 最差效率

最差效率除了 bit stuffing 拉滿，還有就是傳輸的資料量最少，只有 1 個 bit，此時 data field 依舊需要 8 個 bit 的長度，因為 Data length code (DLC) 只告訴我們需要幾個「bytes」。

$$
\frac{1}{8+44+3+10}=0.0153...
$$

10 就是根據上面 bit stuffing 的公式，算出來的：

$$
\left\lfloor \frac{8+34-1}{4}\right\rfloor=10
$$

# Arbitration

下面介紹 CAN 藉由 Identifier 決定優先順序的過程。

- 首先 CAN 有規定每個 node 會在 Start-of-Frame 時同步，也就是要等到 bus 空閒了，大家才可以開始 Arbitration。
- 開始後，電線就像是個大大的 AND gate，每一個 node 傳上去 1 個 bit 時會全部 AND 起來：
- 如果結果是 0，那麼只要該 bit 是 0 的人就留下來繼續傳下個 bit
- 是 1 的人就只能乖乖閉嘴
- 如果結果是 1 ，那麼大家就繼續傳

可以注意到 bit stuffing 不會影響到這個判決結果，因為如果某個 node 有連續 5 個 0，那麼他的優先權一定是最大的，其他人只有可能跟他一樣大，不會比他大。

連續 5 個 1 也是類似的同樣道理。

# Bit Rate

雖然前面有說傳輸速率最高可達 1Mbps，但是實際上會跟 bus 的長度有關，越長則越慢，因為要等到所有人都收到訊息所需的時間就越長。

例如 25m 的 bus 就是可以達到最大 bit rate 的長度，但是 5000m 的 bus 的 bit rate 只有 10kbps...。

---

# CAN 的時間分析

接著是分析所謂的「最差反應時間」，也就是一種 message 的 instance，從發佈到結束總共所需的最長時間。

## Problem Formulation

message 實際上是具有週期性的，會每隔固定時間發佈一個該 message 的 instance。

所以當我們踩下煞車時，並不是立馬做出煞車的動作，而是要位於煞車區的 ECU 收到有關煞車的 message，並且同時偵測到有踩下煞車，才會真的做出反應，像是發送壓緊碟剎的 message 之類的。

下面是分析時常用的代號：

- message：$\mu_{0},\mu_{1},...,\mu_{n-1}$
- 通常沒特別講的話，$\mu_{0}$ 的優先權最大，可以回顧上面的 identifier
- Unique ID (=priority)：$P_{0},P_{1},...,P_{n-1}$
- Transmission Time：$C_{0},C_{1},...,C_{n-1}$
- 這個值可以由傳輸長度除以傳輸速率得到
- Period：$T_{0},T_{1},...,T_{n-1}$

## 前提

- 我們假設從開始到結束的時間一定一樣長，不會有「抖動 jitter」。
- 所有的 message 有無限個 instance
- 所有 message 不一定有對齊

## 限制

在列出公式之前，有以下的限制：

:::warning
最差反應時間不會大於傳輸週期
$$
R_{i}\le T_{i}
$$
:::

- Technical reason
- 如果 $R_{i}>T_{i}$，下面的數學公式不會成立
- Practical reason
- 通常來說一個週期以前的 message 不會比現在的 message 有用

## 公式

公式有兩個部分，下面是第一部分：

$$
R_{i}=Q_{i}+C_{i}
$$

$C_{i}$ 就是自己的傳輸時間。$Q_{i}$ 則是以下第二部分

$$
Q_{i}=B_{i}+\sum_{\forall j,P_{j}<P_{i}}\left\lceil \frac{Q_{j}+\tau}{T_{j}} \right\rceil\times C_{j}
$$

$B_{i}$ 是所謂的 blocking time，他的數值是：

$$
B_{i}=\max_{\forall j P_{j}\ge P_{i}} C_{j}
$$

因為我們的情境下沒有同步，所以會有順位低(或相同)的擋在前面的情況。
>相同是因為有可能前一個同類被一直擋住，最終卡到自己

$\left\lceil \frac{Q_{j}+\tau}{T_{j}}\right\rceil$ 這部分是算在 $Q_{i}$ 的時間內，第 $j$ 種 message 最多可以擋第 $i$ 種幾次，所以後面才會再乘上擋的時間。

$\Sigma$ 裡面整坨又叫做 waiting time。

:::info
$\tau$ 下面會解釋他的存在。總之他是一個常數。
:::

## 計算方法

從公式可以看到，第二部分左右兩側都有 $Q_{i}$，通常解這種問題時常用到的技巧叫做「fix point」演算法。

想要找到 $Q_{i}$ 的值：

- 先將 $Q_{i}$ 設為 $B_{i}$
- 計算公式的右手邊內容得到 RHS
- 如果 RHS + $C_{i}$ > $T_{i}$，直接 stop
- 因為違反 constraint
- 如果 $Q_{i} <$ RHS
- 令 $Q_{i}$ = RHS，然後再次計算 RHS
- 如果 $Q_{i} ==$ RHS
- 找到目標的 $Q_{i}$ 了，可以停止計算(或計算下一個 $Q_{i}$)
- 令 $R_{i}=Q_{i}+C_{i}$

## 回顧限制

1. 為什麼我們會需要 $R_{i}\le T_{i}$ 這個限制？

是因為公式中的這部分：

$$
\sum_{\forall j,P_{j}<P_{i}}\left\lceil \frac{Q_{j}+\tau}{T_{j}} \right\rceil\times C_{j}
$$

是在算第 $i$ 個 task 最多會被擋幾次(擋多久)，但如果沒有保證 $R_{i}\le T_{i}$，那麼擋第 $i$ 個 task 的人，就有可能會是自己的同夥(可能是從很早之前一直被擋到現在的同伴)。

2. 公式中為什麼要有 $\tau$？

原因是出在於取 ceiling 的時候，例如 $\left\lceil \frac{100}{25} \right\rceil=4$ 但是為了「保守起見」，我們會希望讓他多算一次，以防一些意外發生，所以如果加上了 $\tau$，那麼上面的答案就會是 5 而不是 4，

---

# Critical Instant Theorem

:::warning
messsage $\mu_{i}$ 的 $R_{i}$是發生在，當所有優先度比他高的 message 跟他同時 release 的時候。

或者說：

如果所有優先度比他高的 message 跟他同時 release，則 messsage $\mu_{i}$ 的 $R_{i}$ 就會發生
:::

這是上面公式背後的理論；這是必要但不充分條件，也就是說：

:::info
如果 messsage $\mu_{i}$ 的 $R_{i}$ 發生，則所有優先度比他高的 message 「不一定」跟他同時 release
:::

當初這個公式是用在 preemptive 的情境，但 CAN 是個 non preemptive 情境，所以我們上面的公式有額外加上 blocking time 的部分。

## 公式證明

其實只要分段討論就可以證明以下情況 $R_{i}$ 不會更差。

- Case 1：如果不是所有較高順位的同時 release，而是有一些較晚 release
- 有可能 $\mu_{i}$ 會比所有 higher priority 較早 release，那麼 $R_{i}$ 可知會變小
- 或者 $\mu_{i}$ 依舊被某些 higher priority 的擋住，但是因為有一部分的人較晚 release，所以有可能「可以擋的次數變少了」
- Case 2：如果不是所有較高順位的同時 release，而是有一些較早 release
- 如果那些較早 release 的，真的太早就 release，讓 bus 在 $\mu_{i}$ release 前就空閒下來，那麼 $R_{i}$ 不會變差
- 或者說此時可以視為退化成 Case 1 的第二種情形
- 如果那些較早 release 的，使得 bus 在 $\mu_{i}$ release 時依舊 busy
- 假設此時的 $R_{i}$ 是最長的
- 這時我們可以把 $\mu_{i}$ release 的時間往前，移到跟那些較早 release 的 message 同時
- $R_{i}$ 就會是原本的值，加上多往前移動的這段，那麼就會跟原本假設 $R_{i}$ 是最長的矛盾

---

# Generalization to Software Tasks

上面的公式其實也可以推廣到 preemptive 的情形，例如 ECU 的 software task。

公式跟上面很像：

$$
R_{i}=C_{i}+\sum_{\forall j,P_{j}<P_{i}}\left\lceil \frac{R_{j}}{T_{j}} \right\rceil\times C_{j}
$$

由於是 preemptive，所以不會有 blocking time，只要你順位比我小我就直接插隊。

也因此不需要 $\tau$，因為不用去在意誰先誰後，~~只要順位低就沒有人權~~，所 ceiling 發生整除時不用有保守的考量。