---
# System prepended metadata

title: Data Communication
tags: [CSIE, NTNU, 選修, Data Communication]

---

# Data Communication
NTNU 資料通訊
##### [Back to Note Overview](https://reurl.cc/XXeYaE)

{%hackmd @sophie8909/pink_theme %}
###### tags: `NTNU` `CSIE` `選修` `Data Communication`
<!-- tag順序 [學校] [系 必選]  or  [學程 學程名(不含學程的 e.g. 大師創業)] [課程] -->

## Score
-   Homework 45%
-   First Exam 20%
-   Final Exam 25%
-   Participation 5%
-   Attendance 5%

![](https://i.imgur.com/MXtVhAd.png)


## Course 
- Data communication as a network of flows
- Point-to-point communcation vs. end-to-end communication
    - ARQ at the data-link layer vs. Window flow control at the transport layer
- Error detection vs. error correction vs. retransmission
- Data retransmission and/or Passive replication
- Free-for-all multiaccess vs. Perfectly-scheduled multiaccess
    - CAN, Aloha, TDMA and its extension to improve throughput
- Theory and models
    - Data communication as a network of flows (a graph)
    - Network flow algorithm, shortest-path algorithm, etc.
    - Little's throrem, Queueing theory, Markov chains, Poisson process
    - Scheduling for timely data delivery and/or data-loss tolerance
- Protocols and systems
    - CRC, ARQ, multiplexing, CAN, Aloha, TDMA and its extension
    - Real-time communication
    - Fault-tolerant communication
    - flow controls, time synchronization
## OSI layers
![](https://i.imgur.com/GlWeY0g.png)


## Error Detection and Correction
1. single-parity check
2. horizontal and vertical parity check
3. cyclic redundancy check (CRC)
4. Hamming error detection/correction 

### Metrics to evaluate error detection design
1. the minimum distance of a code 
2. the probability that a random bit string will be accepted as error-free
3. the burst-detecting capability
    - the largest integer $B$ such that a code can detect all burst of length $B$ or less


## Hamming Code and Error Correction/Detection
- a **parity check code (or linear code)** is a linear transformation from the string of data bits to the string of data bits and parity checks
    - In general there can be $K$ data bits, and $L$ parity checks
- a **code word** is the result of the transform of a certain parity check code </br>$\to$ a **code word** is the data bits plus parity checks for：
    1. single parity check
    2. horizontal & vertical parity check
    3. cyclic redundancy check(CRC)
### 2.3.1 Single Parity Checks
- Example
    - 1011000 $\to$ 10110001
### 2.3.2 Horizontal and Vertical Parity Checks
### 2.3.3 Parity Check Codes
### 2.3.4 Cyclic Redundancy Checks
1. represent a code word by $X(D)$.
    $$
    X(D)=S(D)\cdot D^L+C(D)
    $$
    - S(D)：its coefficients are data bits
    - C(D)：its coefficients are parity checks
2. choosing a generating polynomial, $g(D)$ and compute $\frac{S(D)\cdot D^L}{g(D)}$, we have:
    $$
    S(D)\cdot D^L=g(D)\cdot z(D)+C'(D)
    $$
3. use the remainder polynomial $C'(D)$ as parity checks
    $$
    \begin{align}
    C(D)&=C'(D)\\
    \implies X(D)&=S(D)\cdot D^L+C(D)\\
    &=g(D)\cdot z(D)+C'(D)+C(D)\\
    &=g(D)\cdot z(D)
    \end{align}
    $$
    which means $g(D)$ divides $X(D)$.
4. send $X(D)$ to the receiver.
5. Now, use $e(D)$ to represent the errors introduce along the sending path. The the receiver will get $Y(D)=X(D)+e(D)$
6. compute $\frac{Y(D)}{g(D)}$, and see whether the $e(D)$ is $0$ or not. If not, we know there's error.
### Hamming Code
#### Definition
- Definition 1: ==**Hamming distance**== 
    - between two code words is the number of different bits between the tow denoted by d(u,v) for code words u and v.
- Definition 2: ==**Hamming Weight**== 
    - of a code word is the number of non-zero bits in it, denoted by wt(u) code word u. 
    - Hamming weight for a **linear code** is **the minimum Hamming weight of any non-zero code word** in the linear word. 
- Definition 3: ==**The Nearest-Neighbor Rule**== 
    - we perform error correction by converting the **received bit vector** into the code word that has **the smallest Hamming distance** to it.
![](https://i.imgur.com/xJedVSf.png)

#### Theorem 
- If the Hamming weight of a linear code is at least 2t+1, then the neatest-neighbor rule can correctly correct any t or fewer errors; alternatively, it can detect any 2t or fewer errors. 

## 2.4 ARQ: RETRANSMISSION STRATEGIES
ARQ: Automatic Repeat Request
- Model and definition, assuming Node A sends frames to Node B ![](https://i.imgur.com/Kn3bc0n.png)

### An initial idea of Stop-and-Wait ARQ
- Node A sends a new packet only if it received an acknowledgement from Node B (called an Ack)
- Node B sends an Ack if the received frame is error-free; otherwise, it sends a negative acknowledgement (called an Nak)
<!-- ## 3.1 INTRODUCTION
### 3.1.1 Multiplexing of Traffic on a Communication Link
## 3.2 QUEUEING MODELS-LITTLE'S THEOREM
### 3.2.1 Little's Theorem
### 3.2.2 Probabilistic Form of Little Theorem
### 3.2.3 Applications of Little's Theorem -->
## Queueing Model and Little's Theorem

### Link delay
- The **processing delay** between the time the packet is 
    - correctly received at the head node of the link 
    - the time the packet is assigned to an outgoing link queue for transmission. 
    - (In some systems, we must add to this delay some additional processing time at the DLC and physical layers.) 
- The **queueing delay** between the time the packet is 
    - assigned to a queue for transmission 
    - the time it starts being transmitted
    - During this time, the packet waits while other packets in the transmission queue are transmitted. 
- The **transmission delay** between the times that 
    - the first and last bits of the packet are transmitted. 
- The **propagation delay** between the time 
    - the last bit is transmitted at the head node of the link
    - the time the last bit is received at the tail node. 
    - This is proportional to the physical distance between transmitter and receiver
    - it can be relatively substantial, particularly for a satellite link or a very high speed link.

### Standard Queueing Theory Nomenclature
1. The **first letter** indicates the nature of the arrival process \[e.g., $M$ stands for memoryless, which here means a Poisson process (i.e., exponentially distributed interarrival times), $G$ stands for a general distribution of interarrival times, $D$   stands for deterministic interarrival times].
2. The **second letter** indicates the nature of the probability distribution of the service times (e.g., $U$, $G$, and $D$ stand for exponential, general, and deterministic distributions, respectively). In all cases, successive interarrival times and service times are assumed to be statistically independent of each other.
3. The **last number** indicates the number of servers. 

- the memoryless property of exponential distribution:
    $P\{x>s+t|x>s\} = P\{x>t\}$
    $x$: interarrival time
### Analyzing efficiency of the stop-and-wait
#### Way #1
- Let $T$ be the total time between the transmission of a packet and reception of its Ack
    - If error free, $T=T_1=T_t+2T_d+T_f$
        >$T_t$：packet transmission time
        >$T_d$：delay in propagation and processing
        >$T_f$：feedback transmission time
    
        ![](https://i.imgur.com/GzU270d.png)
    - With chances of error, $T=T_2=T_1+T_{to}(EX-1)$.
        >$EX=q^{-1}$
        >$EX$：the expected number of times a packet must be transmitted for a stop-and-wait system
        >$q$：the probability that a packet is correctly received and acked on a given transmission
        >$T_{to}$：length of a timer(duration before a time-out)
        >$T_t$：packet transmission time
        >$T_2$：total time between the transmission of a packet and reception of its **Ack**

        ![](https://i.imgur.com/z9PH1Rn.png)
        - setting $T_{to}>T_{1}$, we have $T_2=T_1+T_{to}(q^{-1}-1)>q^{-1}T_1$.
            $$
            \begin{align}
            T_{to}&>T_1\\
            T_{to}(q^{-1}-1)&>(q^{-1}-1)T_1\\
            T_1+T_{to}(q^{-1}-1)&>q^{-1}T_1
            \end{align}
            $$
        - setting $T_{to}<T_{1}$ will cause additional redundancy, but then we have $T_2<q^{-1}T_1$, a way to bound the latency.
#### Way #2
- Define efficiency $E$ as the expected number of packets delivered to node $B$ per frame from $A$ to $B$
    - Efficiency $E = \frac{1}{EX} = q = 1-p$
        >$EX$：the expected number of transmissions before the packet is correctly received
        >$p$：the probability of frame error
        >$q$：the probability of no frame error (q=1-p)
       
         ![](https://i.imgur.com/LtKsYVs.png)
## 3.3 THE $M/M/1$ QUEUEING SYSTEM
### 3.3.1 Main Results

#### the Poisson Process
A stochastic process $\{A(t)|t > 0\}$ with rate $\lambda$ and 
1. $A(t)$ = \# of arrivals in $[0,t]$
2. \# of arrivals occurring in disjoint time intervals are independent
3. \# of arrivals in any intend of length $\tau$ is Poisson distributed with parameter $\lambda\tau$
    $$P\{A(t+\tau) - A(t)=n\}=e^{-\lambda\tau}\frac{(\lambda\tau)^n}{n!},\forall t,\tau > 0$$

######
![](https://i.imgur.com/NlQTIdR.jpg)

![](https://i.imgur.com/ScCg8Qe.png)

$P_{ij} = P\{N_{k+1}= j| N_k = i\}$
### 3.4.1 $M/M/m$: The m-Server Case


## 3.7 TIME REVERSIBILITY-[BURKE'S THEOREM](https://en.wikipedia.org/wiki/Burke%27s_theorem)
The analysis of the $M/M/1$, $M/M/m$, $M/M/\infty$, and $M/M/m/m$ systems was based on the equality of the steady-state frequency of transitions from $j$ to $j + 1$, that is, $p_jP_{j(j+1)}$, with the steady-state frequency of transitions from $j + 1$ to $j$, that is, $p_{j+1}P_{(j+1)j}$.

- [detailed balance equations](https://en.wikipedia.org/wiki/Detailed_balance) 
    - valid for any Markov chain between with integer states in which transitions can occur only between neighboring states
        - [birth-death processes](https://en.wikipedia.org/wiki/Birth%E2%80%93death_process)
    - time reversibility

### Properties of the Reversed Chain:
1. The reversed chain is irreducible(不可約的), aperiodic(非週期性的), and has the same stationary distribution as the forward chain.
2.  
3. 


<!-- p217還有一些東西 -->


### Burke's Theorem
- Consider an $M/M/1$, $M/M/m$, or $M/M/\infty$ system with arrival rate $\lambda$.
- Suppose that the system starts in steady-state.
- Then the following hold true:
    1. The departure process is ***Poisson*** with rate $\lambda$.
    2. At each time $t$, the number of customers in the system is independent of the sequence of departure times prior to $t$
    - Proof on text book ![](https://i.imgur.com/mJjf4VI.png)




---

##### [Bernoulli's Principle](https://en.wikipedia.org/wiki/Bernoulli%27s_principle): $P\{S_n = k\} = \binom{n}{k}p^k(1-p)^{n-k}$
##### [Poisson distribution](https://en.wikipedia.org/wiki/Poisson_distribution)
*[ARQ]: Automatic Repeat Request
*[irreducible]:不可約的
*[aperiodic]:非週期性的
 
## 4.1 
## 4.2 Slotted Multiaccess and the Aloha System

![](https://i.imgur.com/oXhVVyU.png)


$\begin{cases}
P_0(P_{02}+P_{03}+P_{04})&=P_1(P_{10})\\
P_1(P_{10}+P_{12}+P_{13}+P_{14})&=P_2(P_{21}) \\
P_2(P_{21}+P_{23}+P_{24})&=P_0(P_{02})+P_1(P_{12})+P_3(P_{32})\\
P_3(P_{32}+P_{34})&=P_0(P_{03})+P_1(P_{13})+P_2(P_{23})+P_4(P_{43})\\
P_4(P_{43})&=P_0(P_{04})+P_1(P_{14})+P_2(P_{24})+P_3(P_{34})\\
P_0+P_1+P_2+P_3+P_4&=1
\end{cases}\\
\implies\begin{cases}
P_1(P_{10})&=P_0(P_{02}+P_{03}+P_{04})\\
P_2(P_{21})&=P_0(P_{02}+P_{03}+P_{04})+P_1(P_{12}+P_{13}+P_{14})\\
P_3(P_{32})&=P_0(P_{03}+P_{04})+P_1(P_{13}+P_{14})+P_2(P_{23}+P_{24})\\
P_4(P_{43})&=P_0(P_{04})+P_1(P_{14})+P_2(P_{24})+P_3(P_{34})\\
P_0+P_1+P_2+P_3+P_4&=1
\end{cases}$

## 1207
### TDMA Scheduling
- Collision-free TDMA schedule
    - Primary interference
    - Secondary interference
### Graph Theorem
- Terminologies
    - $d(v)$ : degree of node $v$
    - $T_i$ : a set of assigned time slots for node $i$ in a given cycle
    - $|T_i|$ : # of time slots assigned to node $i$ in a given cycle
![憨憨的小畫家graph示意圖](https://i.imgur.com/xrn7ej5.png)
- Defines
    1. **Saturation Condition**
       node $i$ is said to be "saturated" if all links to node $v \in d(i)$ has been assigned with at least one time slot.
    2. **Link Scheduling Criteria**
       $T_u\cap T_i\cap T_j=\emptyset,\forall\text{ node }u\text{ and }i,j\in d(u),i\neq j$

- distributing algorithm
    - M. Luby's algorithm
        - decide independent nodes
            1. generating random number for every nodes
            2. start from any non-finish node
            3. compare itself number to its neighbors
                3.1 if it's the smallest amoung those, color it( is independent node)
                3.2 if not, do nothing
            4. do step 3 to check all non-finish node
            5. a color is finished, repeat step 2.-4. until all node is colored


## 1214
### Industrial Internet of Things (IIoT)
- Synergizing sensing, analytics, and control
    - Cloud 
#### Low-latency → Real-time
- Conceptually, in data communication, **fast enough is good enough**
- Deadline: a way to specify what we meant by fast enough
    - e.g. 自駕車反應時間
- Soft deadlines vs. hard deadlines
    - Missing a soft deadline is not desirable but may be acceptable
        - e.g. life video 
    - Missing a hard deadline will lead  to disastrous consequences
- Soft/hard real-time system: a system that meets soft/hard deadlines

#### Real-time data communications
- For networked applications, 
#### Data communication intermediaries
- Purposes
    - Decoupling senders and receivers
    - Simplifying 
- Example intermediaries: TAO, MQTT, NSQ, ...

#### A model for event processing
- latency requirements
- Temporal semantics:
    - Absolute time consistency on an event's elapse time since creation 
    -  Relative time consistency on the difference between even's creation time

#### Real-time cyber

    


## 1221
- Real-time Fault-Tolerant Data Communication
    - ![](https://i.imgur.com/bwMG6cf.jpg)
    - ![](https://i.imgur.com/bx1Khe5.jpg)
    - ![](https://i.imgur.com/aBr0A5Q.png)
    - ![](https://i.imgur.com/ceOHPy8.png)
    - ARQ
    - MQTT→Mosquitto
        - QoS 0
        - QoS 1: at-least-one semantics
        - QoS 2
    - Different layer deal with different thing ??????
    - strategy 1: Active data replication
        - 傳給所有，最後得到共識
        - state-machine approach
        - pros: low latency
        - cons: high cost
    - strategy 2: Passive data replication
        - primary-back approach
        - 傳給 Primary，Primary 傳給其他 Backup
        - when Primary out of service, backup change to be new primary
        - pros: low cost
        - cons: high latency
        - *lemma 1*
            - $R\leq(N+L)T-\Delta PB - \Delta BB - X$ is the least upper bound of the deadline to do data replication to the backup server. 
                - $\Delta PB$ from pub to primary
                - $\Delta BB$ from primary to backup

## 1228
### Network Flow Control
textbook 6.1~6.2.1, 6.3
#### Motivation
- To let the data transmit in the data network can handle by its capacity
    - maximum flow, maximum cut, bla bla bla...
#### Challenge
 ![](https://i.imgur.com/L7LIEcL.png)
- service requirements
    1. fault tolerance(preventing data loss)
    2. timing delay/data rate(FPS)
#### Objectives
1. limiting delay an buffer overflow
    ![](https://i.imgur.com/2tnz3mn.png)
    ![](https://i.imgur.com/md7femo.png)
2. fairness
    ![](https://i.imgur.com/pZGv0PL.png)
    1. fair in terms of rate
        → $n+1$ flows each having rate of 0.5
        → overall throughput = $(n+1)\over 2$
    2. fair in terms of resource usage
        → $n\over{(n+1)}$ capacity usage
#### Approaches
1. window flow control
    ![](https://i.imgur.com/RfTQUyr.png)
    - $W_{AB}$ : **an upper bound** on the # of data units that have been sent by $A$ and are not yet known by $A$(data sender) to have been received by $B$(data receiver).
    - $k$ : received request number can send data up to seq# $k+w-1$
        ![](https://i.imgur.com/wMGBTiy.png)
    - Delay analysis
        ![](https://i.imgur.com/GM1SNCt.png)
        - $N = T \cdot \lambda$
        - $\rho \cdot W = t \cdot \lambda$, where $0 \leq \rho \leq 1$
        - if w increasing, t increasing
    - case 1 : $d<w\cdot x\implies$ data rate $={1\over x}$
    - ![d畫錯 後面的是對的](https://i.imgur.com/S5qmyC0.png =x300)
        - w is not important, because the sender is keep sending the message. And every $x$ time only get 1 message, so the data rate is $1\over x$
    - case 2 : $d>w\cdot x\implies$ data rate $={w\over d}$
    - ![](https://i.imgur.com/D88UiZX.png =x300)
        - every $d$ time receive/send $w$ #msg 
3. rate control
    - type 1:
    z    ![](https://i.imgur.com/v2vxlO6.jpg)
        - $r$ : minimum data rate, $r=min\{{1\over x},{w\over d}\}$
    - type 2(0104)






## 0104
### Leaky Bucket Flow Control
- Time Synchronization Protocols
    - use Markov chain
        - ![](https://i.imgur.com/O1aCVpT.jpg)
        ![](https://i.imgur.com/719D9ft.jpg)
        - state $i$ : $w-i$ permit available, if $i\leq w$, $i-w$ data pending, otherwise.
        - the probability of $k$ packet arrival at rate $r$ (i.e. in $1\over r$ seconds)
            $$
            a_k=\frac{e^{-\frac{\lambda}{r}}({\lambda\over r})^k}{k!}
            $$
        - special feature : only return state at most 1, because within 1 time step, only 1 new permit available
        - $$
          \begin{align}
          &P_{0i}=\begin{cases}
          a_{i+1}&,\text{if }i\geq 1\\
          a_0+a_1&,\text{if }i=0
          \end{cases}\\
          \text{for }j\geq 1,&P_{ji}=\begin{cases}
          a_{i-j+1}&,\text{if }j\leq i+1\\
          0&,\text{otherwise}
          \end{cases}
          \end{align}
          $$
        - ![](https://i.imgur.com/OF0kctp.png)
        - average delay : ![](https://i.imgur.com/YVabti2.png)
    - NTP accuracy
        - Conventionally, can achieve milliseconds accuracy
            - With improvement, may achieve an accuracy up to tens of microseconds
        - Primary time servers
            - Synced to national standards by radio
            - Accuracy: tens of microseconds
        - Secondary time severs
            - Synced to primary time servers
            - Accuracy: a few hundred microseconds to a few of milliseconds
        - Clock strata
    - NTP topology example
        - Synchronizing clocks along the synchronization paths
    - NTP synchronization basics
        - Suppose that host A is going to synchronize its clock to that of host B
        - Notation
            - $\delta$ : one-way delay
            - $\theta$ : offset between two clocks
        - The mean offset between two clocks is determined by message exchange between A and B
            - ![](https://i.imgur.com/QuQrRui.jpg)
        - Synchronization is performed by gradually reducing the mean offset
    - PTP: precision time protocol
        - Designed to achieve microsecond to sub-microsecond accuracy and precision
        - Spatially localized
        - Administration free
        - Accessible for both high-end devices and low-cost, low-end devices
    - ![](https://i.imgur.com/dIRkMmB.png)
    - ![](https://i.imgur.com/2gbCueX.jpg)

- ![](https://i.imgur.com/7vfjTNM.jpg)

## Final exam
NTP (p10)