# TDMA Based Protocol

繼上次的 CAN，接著介紹其他可能未來與之競爭的協議。

:::info
在 TDMA-based 的 protocol 中，不再是靠 CAN bus 傳輸，而是有一個 Switch 來負責決定當前要傳輸哪個 Signal；所有依靠同個 Switch 的 Signal 都算是同一種 Message。
:::

# TTEthernet

從名字來看，他是 Ethernet 的加料版，多了 TT。

TT 的意思是 Time-Triggered，也就是可以確定 message 何時被送出，不會有 worst case 無限大的情況。

## 特色

- QoS
- 具有優先順序
- preemptive
- Time synchronization

## Traffic types

TTEthernet 傳輸時有分成以下的種類：

- Time-Triggered (TT) traffic (highest priority)
- Sent over the network at predefined (scheduled) time
- 在特定的時間只讓某個 node 來傳；會需要 Global time 的概念，也就是利用 Time synchronization
- TTEthernet 主要的特色，通常會採用的模式
- Rate-Constrained (RC) traffic
- Sent over the network with predefined bandwidth
- 雖然不確定何時送出，但是可以知道保留多少 bandwidth 給予使用
- Best-Effort (BE) traffic (lowest priority)
- Conventional Ethernet
- 就是原本的 Ethernet；基本上沒有給予任何保證；最不常會採用的模式

## 最大的問題

雖然 TTEthernet 提供了像是時間同步跟 TT 這些特色，但是由於其成本太高，導致他相比 CAN 不那麼常被採用。

# Time-Sensitive Networking (TSN)

他也是 Ethernet 的一種延伸。

原本名字叫做 Audio Video Bridging (AVB)，因為他原本是從影音傳輸來的，但是維護者不想讓他只侷限於影音，所以就把他換個名字。

## 特色

跟 TTEthernet 類似：

- QoS
- 具有優先順序，所以高優先度的 message 可以有時間上的保障
- preemptive
- Time synchronization
- 所以可以達到 Global Time，提供 TT 這個特色
- Frame replication and elimination
- 有提供「備份」這個功能，以因應某些 reliability 的需求
- 多傳一份走不同路徑，接收方也要有辦法分辨哪個是備份，或者說有沒有遺失
- 並且還會有 Bridge(Switch) 的結構
- 可以由 Sender 或 Bridge 負責發出備份
- 可以由 Receiver 或 Bridge 負責處理備份
- Time aware shaper
- 為了實現 TT 的一個手段
- 這個結構由「Gate Control List」跟「Time aware Gate」組成
- 每個「Time aware Gate」會對應一個 Queue，可以為每個 queue 制定對應的 priority
- Gate Control List 有兩個要素，一個是週期，一個是每個 tick 的內容
- 每個 tick 的內容就是決定當前時間哪個 gate 有開啟
- 週期就是會以此為循環

當然 TSN 也不只用於車聯網，也可以用於工控系統等。

:::warning
由於其具有 TT 以及 Reliability 的特色，所以是目前認為最有可能跟 CAN 競爭的對手
:::

# Other protocol with TDMA concept

例如 FlexRay。

總之以上的協議因為都具有 TT 這個特色，又叫 TDMA，都是透過時間來區分誰可以使用該區間的資源。

後面的時間分析不去細分是哪種協議，而是去分析「TDMA based」這種協議。

## Abstraction

上面提到：

:::info
後面的時間分析不去細分是哪種協議，而是去分析「TDMA based」這種協議。
:::

這裡就是使用了「抽象化 Abstraction」這個技巧。

根據 wiki 的定義，「抽象化 Abstraction」的意思是「去掉細節，保留核心概念」的這個「過程」，或者是這個過程的結果。

因為我們不是真的去業界做東西，我們希望普遍地分析，所以才會改成去分析那些 protocol 的共同有的核心概念，TDMA based 的 protocol。
>在分析 CAN 的時候也有用到，我們不去仔細討論 protocol 的細節
>因為我們只是想知道 non preemptive 且具有 priority 的情境下反應時間會是如何

:::warning
在做或是思考 Generalization 的問題或事情時候，適時的使用抽象化這個技巧，可以幫助我們觸及問題的核心 ：)
:::

---

# TDMA-based Problem Formulation

首先腦中想像一個時間軸被切成好多等分，這些等分中，有些可以用來傳輸的叫做「time slot」，這些「time slot」可以來分配給很多不同的 message。

這些「time slot」的分佈以及「message arrival」的分佈又叫做「pattern」。
>「time slot」的分佈又叫做 network schedule pattern
現在的問題是：

:::info
如果給定了 network schedule 跟 message arrival patteren，那麼 message 的最差反應時間是多少
:::

## 假設

跟 CAN 一樣我們也有給予一些假設

- 每個「time slot」都一樣長
- 每個「time slot」只有恰好一個「instance/frame」
- 「instance/frame」只有當「time slot」「完整」的時候才會傳輸
- 也就是開始跟結束都在「time slot」裡面

:::warning
這個跟 CAN 相比會比較輕鬆，因為 TDMA based 只需要知道自己的 pattern 就可以進行分析，不需要知道其他人長怎樣。
:::

## Message Type

有兩種：

- Synchronous：知道每個 Frame 在何時會到達
- 例如 TTEthernet 的 Time-triggered traffic
- 跟 TSN TSNtraffic
- Asynchronous：不知道每個 Frame 在何時會到達，但是知道「pattern」長怎樣
- 例如 TTEthernet 的 Rate-Constrained traffic
- 跟 TSN 的 AVB traffic

## Pattern

用來描述 frame/message arrival 跟 time slot schedule 的方法。
>message 在這裡似乎被更常叫做 frame

- Frame arrival pattern：(m,p,a~1~,a~2~,...,a~m~)
- Schedule pattern：(n,q,s~1~,s~2~,...,s~n~)

>速記：m for message,a for arrival,s for schedule

m 跟 n 其實都是指「次數」，p 跟 q 都是指「週期」，只不過為了方便區分所以用不同的記號。

後面的 a~m~ 跟 s~n~ 都是指到達的時間。

例如：
- 有個 frame arrival pattern 為 (2,4,0,3)，代表有兩個 frame，週期是 4，分別在時間為 0 跟 3 的時候抵達
- 有個 schedule pattern 為(2,4,1,2)，代表有兩個 time slot，週期是 4，分別在時間 1 跟 2 的時候開始一個 time slot。

## Not Schedulable

如果$\frac{m}{p}>\frac{n}{q}$，則這樣的情況下是 Not Schedulable，因為 $\frac{m}{p}$ 代表單位時間內有多少 frame，$\frac{n}{q}$ 則是單位時間內有多少 time slot。

如果是大於，就代表 frame 無法傳完，會持續累積下去。

:::warning
這個方法也可以用於評估 CAN 是否為 Schedulable
:::

---

# 時間分析 Synchronous

理論如下：

:::info
只需要考慮 2 rounds 就可以決定最差反應時間
:::

1 個 round 是指 p 跟 q 的最小公倍數。

以上面的例子舉例：

- frame arrival pattern 為 (2,4,0,3)
- schedule pattern 為(2,4,1,2)

由於 p 跟 q 都是 4，所以 1 個 round 就是 4 tick。所以我們只要考慮 8 個 tick 內發生的事情就可以找到最差反應時間。

以下請服用講義 12 頁的圖。

講義實虛線箭頭上的數字代表第幾個 message，上面灰色大括弧的數字是第幾個 round，黃色區域是 time slot。

可以看到在第一個 round 的第一個 time slot，會被第一個 message 使用，但是第二個 time slot 結束時第二個 message 才到來，也就延後到了第二個 round 才被用到。

總之以此規律往下畫就可以發現後續的每個 message 的反應時間都是 3 個 tick，同時也是最差反應時間。

## 為什麼只要 2 個 round

有個關鍵觀察：

:::info
第 1 個 round 跟 第 2 個 round 沒有被分配到 time slot 的數量是一樣的
:::

例如上面每個 round 都是固定 1 個 message 沒有 time slot 可以用。

原因也很簡單，1 個 round 裡面就固定那麼多 time slot 可以用，同時也是固定那麼多 message 發出來，兩者都是固定的數量。

第 1 round 的時候沒有被分配到的那些人是怎麼來的呢？只有兩種可能：

- 到最後一個 time slot 時沒排到，被擠出來的
- 這時再判斷是不是 Not Schedulable
- 如果是 Schedulable 叫做 Case 1
- 出現位置在最後一個 time slot 之後，導致沒有排到
- 這種叫做 Case 2

### Case 1

我們把最後一個 time slot 之前的 slots 叫做「空閒區域」，令在最後一個 time slot 開始的時刻有 y 個人在排隊，接著來仔細思考以下情形：

- 如果 1~st~ round 擠出的 x 人，加上 2~nd~ round 除去那 y 個人，**無法**在空閒區域得到自己的 time slot
- 那就代表一定會有多出一些人堆在那 y 個人前面
- 那就代表人會越堆越多，跟我們一開始的 Scheduable 矛盾

所以可以知道空閒區域一定可以處理掉 x 人加上下一 round 除去 y 個人。

同時也就知道不管是哪一 round 都會有 x 人被擠出來。

### Case 2

這種情形比較好想。一樣把最後一個 time slot 之前的 slots 叫做「空閒區域」，接著仔細思考以下情境：

- 如果 1~st~ round 因為遲到而沒排到的人，在 2~nd~ round 跟那些人一起排隊時，卻導致 2~nd~ round 有 x 人遲到之外，還多了一些人也沒排到
- 那就代表之後的人會越堆越多，也就跟我們一開始的 Scheduable 矛盾

所以可以知道空閒區域一定可以處理掉 x 人加上下一 round 除去 x 個人。

同時也就知道不管是哪一 round 都會有 x 人被擠出來。

---

# 時間分析 Asynchronous

由於兩者都不知道確切到來的時間點，只知道 pattern，所以在討論的時候通常都是固定 time slot 的位置，然後以 frame 的 arrival 做「平移」。

:::warning
一樣請參考講義的圖
:::

在第 14 頁的範例圖中，可以知道平移這件事對於一個實數軸來說有無限種可能，不可能每種都給他試試，不然你會逝世。

不過好在偉大的前人給了我們一個好用的理論：

:::info
$P_i$ 是某個 frame，$S_j$ 是某個 time slot。
如果 $P_i$ 的最差反應時間，發生在 $P_i$ 被分配到 $S_j$ 的時候，則滿足下面兩項：
- $P_i$ 或 $P_i$ 之前的某個 frame 一定要「恰好錯過 / just miss」其分配到的 time slot
- 所謂「恰好錯過 / just miss」的意思是一眼看去他跟 $S_k$ 開始時間是對齊的，但是實際上他錯過了，他分配到的是 $S_{k+1}$
- 在 just miss 的那個 slot 結束開始，到 $S_j$ 開始之前的這段時間內，必定不會有「沒有使用」的 time slot
:::

## 證明

證明很簡單，就是使用「若 P 則 Q，非 Q 則 非 P」；也就是下面兩項只要有一項不成立，那麼 $P_i$ 被分配到 $S_j$ 的時候，就不會是他的最差反應時間發生的時候。

- 第一項很簡單，如果 $P_i$ 之前的每個 frame 都沒有人有 just miss，我們可以隨便選一個 frame，假設他對到 $S_{k}$，然後以他為中心整個往前移動到 $S_{k-1}$，但是 just miss $S_{k-1}$
- 這樣一來我們保持原本的 frame 跟 slot 的分配關係，但是讓時間變得更長了
- 就會跟原本最差反應時間的假設矛盾
- 第二項要分段討論
- 如果發生 just miss 的就是 $P_i$
- 根據上面的敘述，意思就是假設 $S_{j-1}$ 跟 $S_{j}$ 之間有沒有用到的 slot
- 但是這根本不可能發生，$S_{j-1}$ 跟 $S_{j}$ 之間不會有 time slot
- 如果發生 just miss 的是 $P_i$ 的前面某個 $P_k$
- 跟第一項類似，因為可以隨便在 $P_k$ 之後的某個 frame 之中(包含$P_i$)
- 隨便挑一個 frame 為中心往前平移
- 直到跟對應的前一個 slot just miss，就可以保持分配關係一樣，但是反應時間更長

# Asynchronous 最差反應時間公式

有了上面的理論後，根據第一項，可以得到一個關鍵觀察：

:::warning
$P_i$ 或 $P_i$ 之前的某個 frame 一定要「恰好錯過 / just miss」其分配到的 time slot
:::

可以知道我們想找的最差反應時間敘述如下：

:::info
第 i 個 frame just miss 第 j 個 time slot 的時候，其後面第 k-1 個 frame 的最差反應時間。
:::

所以我們只要搜索這些範圍就行了。

公式如下：

$$
1+\max_{1\le k \le m}\left(\max_{1\le j \le n}(s_{j+k}-s_{j})-\min_{1\le i \le m}\left(a_{i+k-1}-a_{i}\right) \right)
$$

上面的公式的意思是，$P_{i}$ just miss $S_{j}$，並計算 $P_{i+k-1}$ 的反應時間。

- 最左邊的 1 是傳輸時間，前面有提到此處都假設一樣，設為 1 tick
- 最外層的 $\max_{1\le k \le m}$，意思是從這 k 個算好的最差反應時間中，在挑出更差的
- 內層就是在算 $P_{i+k-1}$的反應時間

- $\max_{1\le j \le n}(s_{j+k}-s_{j})-\min_{1\le i \le m}\left(a_{i+k-1}-a_{i}\right)$ 的部分
- 假設 $k=1$，此時我們要找 $P_i$ 的最差反應時間，其實就是看哪兩個 time slot 間距最長，不需要在意 frame 的 arrival 時間
- 假設 $k=2$，此時我們要找 $P_{i+1}$ 的最差反應時間
- 此時可以發現後面就多了 $\min_{1\le i \le m}\left(a_{i+1}-a_{i}\right)$ 這個部分，兩者的 $i+1$ 是剛好有對應到的，意思就是看哪兩個 frame 間距最短，**也就是 $P_{i+1}$ 越早開始等待。這部分是 $P_{i+1}$ 尚未開始等待的時間。**
- 而前面則是 $\max_{1\le j \le n}(s_{j+2}-s_{j})$，因為 $P_{i}$ just miss $S_{j}$，所以 $P_{i}$ 實際上是分配在 $S_{j+1}$，也導致$P_{i+1}$ 實際上是分配在 $S_{j+2}$，在算的是相距為 2 的哪兩個 slot 間距最長
- 最終要把 slot 相距的時間，減掉 $P_{i+1}$ 沒有開始等待的時間，就會得到 $P_{i+1}$ 等待的最長時間
- k = ... 以此類推

:::warning
上面簡單來說就是用最密的 arrival pattern 撞上最疏鬆的 frame arrival pattern
:::

## Duplication

由於上面公式中的 i 跟 j 都是從 1 到 m 跟 n，再加上 k 的話最多會超過，所以：

- 首先我們會把原本的 pattern 轉型，讓 p 跟 q 的等於他們的最小公倍數，同時將 m, n 以及 a 和 s 的部分都做擴充
- 為了方便計算超過的部分，會把原本 a 跟 s 的部分後面多複製一份出來，值要照 pattern 接著寫，但是 m,n,p,q 保持不變

這樣一來就可以輕鬆的查找 $s_{j+k}$ 跟 $a_{i+k-1}$ 是多少了。

例如：

- frame pattern 原本是 (m=4,p16,a=3,7,11,15)
- 擴充後就會變成 (m=4,p16,a=3,7,11,15,,19,23,27,31)
- 此時 $a_1=3,a_5=19$
- schedule pattern 原本是 (n=4,q=16,s=0,1,2,3)
- 擴充後變成 (n=4,q=16,s=0,1,2,3,16,17,18,19)

---

# 最佳的 shceduling

- 對於 Synchrnous 來說
- 因為你知道 message 什麼時候來，所以只要讓 time slot 都可以在 message 來的那剎那剛好到
- as early as possible
- 對於 Asynchrnous 來說
- 每個 message 來的越平均越好，因為無法確定準確的時間點
- as evenly as possible

:::danger
不確定 as early as possible 的意思
:::

## Gaps to a practical protocol

- 上面是假設每個 slot 有相同長度
- 並且每個 slot 使提供給 1 個 message 使用
- 不同的 protocol 描述 pattern 的方法都不一樣
- 目前的情境只考慮 1 個 switch，如果是 Multiple Switches 又會不一樣

---

# Real Time Calculus (待補)

:::danger
怎麼直接飆車了老師 :_)
:::