[Home Page - Introduction to Computer Network](/@roger61205/Introduction-to-Computer-Network)
[Home Page - Wireless Communications and Mobile Networks]()
[toc]
# Services
## Framing and Link Access
1. It encapsulates datagram into frame, adding header, trailer.
2. It accesses channels if shared medium
3. “MAC” addresses in frame headers identify source, destination (different from IP address.
## [Reliable Delivery between Adjacent Nodes](/@roger61205/Introduction-to-Computer-Network-Transport-Layer#Reliable-Data-Transfer)
It is seldom used on low bit-error links.
## Flow Control
It paces between adjacent sending and receiving nodes
## Error Detection and Error Correction
### Introduction
* `EDC`: Error detection and correction bits
* `D`: Data protected by error checking
### Methods
#### Parity checking
#### Internet Checksum
1. Sender
1. It treats contents of UDP segment (including UDP header fields and IP addresses) as sequence of 16-bit integers
2. It put checksum (addition (one's complement) of segment content) value into UDP checksum field.
2. Receiver
1. It computes checksum of received segment
2. It checks if computed checksum equals checksum field value
#### Cyclic Redundancy Check (CRC)
1. Terminology
1. $D$: Data bits (given)
2. $G$: Bit pattern (generated), of $r+1$ bits (given)
2. How it works?
1. In this method, we choose $r$ CRC bits, $R$, such that $<D,R>$ exactly divisible by $G$.
2. Receiver knows $G$ and will divides $<D,R>$ by $G$. If non-zero remainder, then there is an error detected.
3. It can detect all burst errors less than $r+1$ bits
## Half-Duplex and Full-Duplex
With half duplex, nodes at both ends of link can transmit, but not at same time.
## Frequency Hopping
:::info
:::
Frequency Hopping is a wireless communication technique where the data signal is rapidly switched among many frequency channels, using a pseudorandom sequence known to both the transmitter and receiver.
# Where is the link layer implemented?
Link layer is implemented in network interface card (NIC) or on a chip.
# Interface Communication
## Sending Side
1. It encapsulates datagram in frame
2. It adds error checking bits, reliable data transfer, flow control, etc.
## Receiving Side
1. It looks for errors, reliable data transfer, flow control, etc.
2. It extracts datagram, passes to upper layer at receiving side.
# Multiple Access Protocols
Multiple access protocols are designed to distribute algorithm that determines how nodes share channel because communication about channel sharing must use channel itself.
## Two Types of Links
1. Point-to-Point
2. Broadcast
## Board Classes
1. When one node wants to transmit, it can send at rate $R$.
2. When $M$ nodes want to transmit, each can send at average rate $R/M$.
3. It is fully decentralized.
### Channel Partitioning
#### Time Division Multiple Access (TDMA)
1. Channel are accessed to in “rounds”
2. Each station gets fixed length slot
$$
length = packet\ transmission\ time
$$
in each round.
3. Unused slots go idle
#### Frequency Division Multiple Access (FDMA)
1. Channel spectrum is divided into frequency bands
2. Each station is assigned fixed frequency band
3. Unused transmission time in frequency bands go idle
#### Code Division Multiple Access (CDMA)
#### Orthogonal Frequency Division Multiplexing (OFDM)
A single data stream is split across multiple closely spaced frequencies.
### Random Access
#### Slotted ALOHA
1. Assumptions
1. All frames have the same size.
2. Time is divided into equal.
3. Nodes start to transmit only slot beginning.
4. Nodes are synchronized.
5. If 2 or more nodes transmit in slot, all nodes detect collision.
2. Operation
When node obtains fresh frame, transmits in next slot
1. If No Collision: Node can send new frame in next slot
2. If Collision: Node retransmits frame in each subsequent slot with probability $p$(why) until success
3. Pros and Cons
1. Pros
1. Single active node can continuously transmit at full rate of channel
2. It is highly decentralized
2. Cons
1. Collision and wasting slots
2. Idel slots
3. Nodes may be able to detect collision in less than time to transmit packet
4. Clock synchronization
4. Efficiency
Suppose $N$ nodes with many frames to send, each transmits in slot with probability $p$
1. Probability that given node has success in a slot: $p(1-p)^{N-1}$
2. Probability that any node has a success $Np(1-p)^{N-1}$
3. Max Efficiency: Find $p^*$ that maximizes $Np(1-p)^{N-1}$
4. For many nodes, take limit of $Np^*(1-p^*)^{N-1}$ as $N$ goes to infinity, which gives
$$
max\ efficiency = \frac{1}{e}=0.37
$$
#### Pure ALOHA
Collision probability increases with no synchronization. Frame will be sent at $t_0$ collides with other frames sent in $[t_0-1,t_0+1]$
#### CSMA (Carrier Sense Multiple Access)
1. Introductions
1. Simple CSMA
It listens before transmits
1. If channel sensed idle, then transmits entire frame
2. If channel sensed busy, then defers transmission
2. CSMA/CD (CSMA with Collision Detection)
1. Collisions are detected within short time
2. Colliding transmissions are aborted, reducing channel wastage
3. Collision detection is easy in wired, difficult with wireless
2. Collision and CD
1. Collision
Collisions can still occur with carrier sensing. If collisions happens, entire packet transmission time will waste.
2. CD
1. Introductions
CSMA/CS reduces the amount of time wasted in collisions
2. Ethernet CSMA/CD Algorithm
1. NIC receives datagram from network layer, creates frame
2. If NIC senses channel
1. If idle, then starts frame transmission.
2. If busy, then waits until channel idle, then transmit
3. If NIC transmits entire frame without collision, NIC is done with frame.
4. If NIC detects another transmission while sending, then sends jam signal
5. After aborting, NIC enters binary (exponential) backoff:
After $m$th collision, NIC chooses $K$ at random from $\{0,1,2, …, 2m-1\}$. NIC waits $K\cdot512$ bit times, returns to Step $2$
* More collisions cause longer backoff interval
3. Efficiency
$$
efficiency = \frac{1}{1+5t_{prop}/t_{trans}}
$$
* $t_{prop}$: The max propagation delay between $2$ nodes in LAN
* $ t_{trans}$: The time of transmitting max-size frame

:::info
$efficiency=1$ when $t_{prop}=0$ or $t_{trans}=\infty$.
:::
### "Taking Turns"
#### Polling
Master node “invites” other nodes to transmit in turn
* Concerns
1. Polling overhead
2. Latency
3. Single point of failure (master)
#### Token Passing
It controls token passed from one node to next sequentially.
* Concerns
1. Token overhead
2. Latency
3. Single point of failure (token)
## Cable Access Networks with Different Board Classes
### Downstring and Upstring
1. Multiple Downstream (Broadcast) FDM channels
* Single CMTS transmits into channels
2. Multiple Upstream Channels
All users contend (random access) for certain upstream channel time slots; others assigned TDM
### DOCSIS (Data over Cable Service Interface Specificaiton)
1. FDM is over upstream, downstream frequency channels
2. TDM Upstream
1. Some slots are assigned, and some have contention.
2. Downstream MAP Frame: It assigns upstream slots
3. Request for upstream slots (and data) transmitted random access (binary backoff) in selected slots.

**Reference**
NCKU 1102_F723500 Introduction to Computer Network
Computer Networking: A Top-Down Approach 8th edition Jim Kurose, Keith Ross Pearson, 2020
NCKUCSIE 1121_F721700 Wireless Communications and Mobile Networks
Introduction to Wireless & Mobile Systems, 4th, by Edition Agrawal and Zeng