2025-03-252025-05-27Lecture Notes

Lecture Notes: Data Communications and Networking

COMP3003 Data Communications and Networking

Dr. Ricky Yuen-Tan HOU

Chapter 1: Basic Concepts

1. Introduction to Data Communications

What is Data Communication?

Telecommunication: Communication over a distance.
Data: Any meaningful information in agreed-upon formats.
Data Communication: Exchange of data between two devices using a transmission medium (e.g., cables, wireless).

`Five Key Components`:

Message – The data being transmitted.
Sender – The device that sends the data.
Receiver – The device that receives the data.
Transmission Medium – The path (wire, fiber, air) the data travels.
Protocol – A set of rules governing data communication (e.g., signaling, encoding, decoding).

2. Network Protocols

Protocols control communication behavior: format, order of messages, and actions triggered by message reception.
Communication Node: Any machine involved in data exchange.

3. `Data Flow Types`

Simplex: One-way communication (e.g., keyboard to computer).
Half-Duplex: Two-way communication, but only one direction at a time (e.g., walkie-talkie).
Full-Duplex: Two-way simultaneous communication (e.g., phone calls).

4. Analog vs. Digital Signals

Analog:

Continuous electrical signals.
Vary smoothly over time.

Digital:

Discrete signals with specific levels (e.g., 0 or 1).
More resistant to noise, easier to store and process.

5. `Digital Encoding Schemes`

`Non-Return-to-Zero (NRZ)`:

1 = High level, 0 = Low level.
Synchronization issues if too many identical bits in a row.
长时间连续的 0 或 1 会导致信号不变，接收方可能失去时钟同步（不知道什么时候开始/结束一个比特）。

`Manchester`:

0 = Low to High transition.
1 = High to Low transition.
Combines clock and data signals.

`4B/5B Encoding`:

4 bits of data mapped to 5-bit code.
Ensures enough transitions for clock synchronization.

6. Analog Signal Transmission of Digital Data

Amplitude Modulation (AM):

Change amplitude to represent 1s and 0s.

Frequency Modulation (FM):

Change frequency to represent bits.

Phase Modulation (PM):

Change phase for 1s, maintain for 0s.

7. Converting Analog to Digital – PCM

Pulse Code Modulation (PCM):
- Sampling -> Quantization -> Encoding
- Sample analog signal at high frequency.
- Each sample is quantized into bits.
- Common in digital audio (e.g., telephony).

8. `Channel Capacity Theorems`

`Nyquist Theorem`:

Ideal, noise-free condition.
Formula: $$B = 2F \times \log_{2}{M}$$

`Shannon’s Theorem`:

Realistic, with noise.
Formula: $$B = F \times \log_{2}{1 + \frac{S}{N}}$$
S/N (Signal-to-Noise Ratio) is often measured in decibels (dB).
Formula: $$SNR_{dB}=10\log_{10}{SNR}$$

9. Computer Networks

What is a Network?

A collection of interconnected devices (nodes) that share data.

Network Categories:

Local Loop – Last-mile connectivity (e.g., DSL, cable).
LAN – Local Area Network (e.g., office/building).
MAN – Metropolitan Area Network (e.g., city-wide cable).
WAN – Wide Area Network (e.g., country-to-country internet).
Internetwork – Collection of interconnected networks.

10. `Network Topologies`

`Bus`

All devices share a single cable.
Simple but vulnerable to cable failure.

`Ring`

Devices form a closed loop.
Data travels in one direction.

`Star`

All nodes connect to a central hub.
Easy to manage but hub is a single point of failure.

`Tree`

Hierarchical combination of star and bus topologies.
Expandable, good for schools/campuses.

`Mesh`

Every device connects to every other.
High reliability but complex and expensive.

11. Network Software & Protocol Hierarchies

Why Layering?

Simplifies design and maintenance.
Promotes interoperability across systems.
Each layer handles specific tasks and offers services to the layer above.

Design Issues:

Addressing
Error detection and correction
Flow control
Routing
Data sequencing

12. Connection-Oriented vs Connectionless Services

Connection-Oriented:

Establish connection first.
Maintain state during communication.
Guarantees delivery and order.
Example: TCP, File Transfer.

Connectionless:

No setup; each packet is independent.
Faster, less reliable.
Example: UDP, streaming media.

13. Service Primitives (APIs for Communication)

Primitive	Meaning
LISTEN	Wait for incoming connection
CONNECT	Establish connection with a peer
RECEIVE	Wait to receive message
SEND	Send a message
DISCONNECT	Close the connection

14. `Reference Models`

OSI Model – 7 Layers

Physical Layer – Transmit raw bits (cables, voltage).
Data Link Layer – Error detection, framing.
Network Layer – Routing (IP).
Transport Layer – Reliable delivery (TCP).
Session Layer – Manage sessions (e.g., login).
Presentation Layer – Data format, encryption.
Application Layer – User apps (HTTP, FTP, SMTP).

TCP/IP Model (More practical)

Link Layer
Internet Layer (IP)
Transport Layer (TCP/UDP)
Application Layer

15. Information Flow in TCP/IP Model

Data moves down the protocol stack at sender:
- App → Transport → Internet → Link
Data moves up the stack at receiver:
- Link → Internet → Transport → App

Chapter 2: Physical Layer

1. Overview of the Physical Layer

The physical layer is the lowest layer in the OSI model. It is responsible for transmitting raw bits over a physical medium, dealing with the mechanical, electrical, and procedural interfaces.

2. Fourier Analysis in Communications

What is Fourier Analysis?

Introduced by Joseph Fourier, this mathematical technique shows that:

Any periodic signal can be represented as the sum of sine and cosine waves of different frequencies, amplitudes, and phases.

`Why is Fourier Analysis important?`

Purpose: Transform signal from time domain to sequence domain; Break down any complex signal into a combination of simple sine and cosine waves.
Why we need: It helps us understand **how signals behave in both time and frequency domains**.
Essential for:
- Signal decomposition
- Bandwidth determination
- Filtering and signal transmission design

Key Terms:

$g(t)$: The original periodic signal
$T$: The signal period
$f = 1/T$: Fundamental frequency
$a_n$, $b_n$: Coefficients representing amplitudes of harmonics

3. Transmission Media

`Categories of Transmission Media`:

A. `Guided Media` (have physical path)

Use solid materials (like cables) to transmit signals.
Types:
- Twisted Pair Cable
- Coaxial Cable
- Fiber Optic Cable

B. Unguided Media (no physical path)

Use electromagnetic waves to transmit through air or vacuum.
Common in wireless communication.

4. Guided Transmission Media

A. Twisted-Pair Cable

Composed of two insulated copper wires twisted around each other.
Types:
- UTP (Unshielded Twisted Pair)
- STP (Shielded Twisted Pair)
Commonly used in LANs and telephone lines.
Connectors: RJ-45

B. Coaxial Cable

Structure:
- Central copper conductor
- Insulating layer
- Outer metallic shield
- Protective plastic sheath
Better noise resistance than twisted-pair
Connectors: BNC

C. Fiber Optic Cable

Uses light to carry data
Structure:
- Core: transmits light
- Cladding: reflects light into the core (lower refractive index)
- Jacket: protects the cable
Modes:
- Single-mode: long-distance, high speed
- Multimode: short-distance, wider core
Advantages:
- Immune to EMI
- Very high bandwidth
Connectors: SC, ST, LC types

5. Unguided Transmission Media (Wireless)

Characteristics:

No physical conductor
Transmission via electromagnetic waves
Applications: Bluetooth, Wi-Fi, Cellular networks

Two common encoding techniques:

Frequency Hopping Spread Spectrum (FHSS)
- Example: Bluetooth
- Signal hops between different frequencies
Direct Sequence Spread Spectrum (DSSS)
- Example: CDMA (used in mobile networks)
- Signal spread over a wider frequency band

6. Electromagnetic Spectrum

Wireless communications operate on various parts of the spectrum:
- Radio Waves
- Microwaves
- Infrared
- Visible Light
Each range has different applications and properties

7. `Wireless Propagation Methods`

A. Omnidirectional Propagation

Transmit and receive signals in all directions
Example: Wi-Fi routers

B. Unidirectional Propagation

Signal directed in a specific direction
Example: Satellite dish, microwave towers

8. Types of Wireless Transmission

A. Radio Transmission

Broadcast communication
Used in AM/FM radio, TV, cordless phones

B. Microwave Transmission

High-frequency radio waves
Used for:
- Long-distance telephone communication
- Satellite links
- TV broadcasting

C. Infrared Transmission

Used for short-range communication (e.g., TV remote)
Cannot pass through walls

D. Lightwave Transmission

Uses lasers or LEDs
Line-of-sight required
Applications: Optical wireless systems

9. Communication Satellites

Act like a microwave repeater in the sky
Process:
1. Receives signal from Earth
2. Amplifies it
3. Rebroadcasts at a different frequency to another location
Used in:
- Global broadcasting
- GPS
- Long-distance communication

考点精选

Fourier Analysis
- Purpose:
  - Break down any complex signal into a combination of simple sine and cosine waves.
  - Transform signal from time domain to sequence domain
- Why we need:
  - It helps us understand how signals behave in both time and frequency domains.
Class of

Medium	Guided/Unguided	Max Distance	Speed	Cost	Interference
Twisted Pair	Guided	Short	Medium	Low	High
Coaxial Cable	Guided	Medium	Medium-High	Medium	Medium
Fiber Optic	Guided	Very Long	Very High	High	Very Low

Type	Frequency Range	Propagation Path	Typical Use Cases
1. Ground Propagation	Below 2 MHz	Travels along the surface of the Earth (ground waves)	AM radio, maritime communication
2. Sky Propagation	2 – 30 MHz	Reflected off the ionosphere back to Earth (sky waves)	Shortwave radio, long-distance HF
3. Line-of-Sight Propagation	Above 30 MHz	Straight-line paths; limited to visible horizon (LOS waves)	FM radio, TV, microwave, satellite

Chapter 3: Data Link Layer

1. Overview

数据链路层是 OSI 模型中的第二层，位于物理层之上，主要负责在相邻节点之间实现可靠的数据传输。
数据链路层的三个核心功能是：

帧封装（Framing）：将比特流划分为帧，使得每个帧在传输过程中可以被区分和识别。
错误控制（Error Control）：检测并纠正数据传输中的错误，确保数据完整性。
流量控制（Flow Control）：管理发送和接收端的速度，避免接收端被发送端的数据压垮。

2. `Framing`

Definition: Dividing a bit stream into discrete frames for transmission.
Methods:
1. Character Count:
  - A header field specifies the number of characters in the frame.
  - Pros: Simple.
  - Cons: Vulnerable to errors in the count field.
2. Flag Bytes with Byte Stuffing:
  - Frames start/end with special flag bytes (e.g., unique patterns).
  - If flag byte appears in data, an escape byte (ESC) is inserted before it.
  - Example: Data “FLAG” → “ESC FLAG”.
3. Starting/Ending Flags with Bit Stuffing:
  - Uses a special bit pattern (e.g., 01111110) to mark frame boundaries.
  - Inserts a 0 after five consecutive 1s in data to avoid mimicking the flag.
  - Example: Data “011111” → “0111110”.

3. `Error Control`

错误控制机制的目的是检测和纠正传输中的错误，确保数据的准确性。

Error Detection

Parity Check:
- Single-Bit Parity:
  - Adds a parity bit to make the total number of 1s even (even parity) or odd (odd parity).
  - Limitation: Detects only single-bit errors.
- Two-Dimensional Parity:
  - Data arranged in a matrix; parity computed for each row and column.
  - Advantages: Detects and corrects single-bit errors using row/column indices.
Cyclic Redundancy Check (CRC):
- Treats bit streams as polynomials (e.g., $101 = x^2 + 1$).
- Uses modulo-2 arithmetic (no carry/borrow).
- Steps:
  1. Sender and receiver agree on a generator polynomial $G(x)$.
  2. Append $r$ zero bits (where $r =$ degree of $G(x)$) to the frame.
  3. Divide frame by $G(x)$ using modulo-2 division; append remainder as checksum.
  4. Receiver divides received frame by $G(x)$; non-zero remainder = error.
- Strength: Detects burst errors effectively.

Error Correction

错误纠正是通过冗余位让接收方在发生错误时进行纠正。常用的错误纠正方法包括：

Forward Error Correction (FEC)

原理：发送方在数据中添加冗余位，接收方可以在没有请求重传的情况下，依据冗余位来纠正错误。
Maps m-bit data into n-bit codewords ($n = m + r$, where r = redundant bits).
Hamming Distance: Number of bit differences between two codewords (e.g., 00000 vs. 00111 = 3).
Receiver corrects errors by selecting the nearest valid codeword.

Hamming Code

Corrects single-bit errors.
Structure:
- Check bits at positions 1, 2, 4, 8, etc. (powers of 2).
- Data bits in remaining positions.
Computation:
- Number of check bits ($r$) satisfies: $2^r \ge m + r + 1$ ($m$ = data bits).
- Each check bit ensures parity for a specific bit combination.
Example: For 7 data bits “1001000”:
- Check bits at 1, 2, 4; compute parity; detect/correct errors via counter.

4. `Flow Control`

Purpose: Prevents sender from overwhelming receiver.
Approaches:
1. Feedback-Based: Receiver sends status updates to sender.
2. Rate-Based: Built-in mechanism limits transmission rate.
Protocols:
1. Stop-and-Wait Protocol:
  - Sender transmits one frame, waits for acknowledgment (ACK).
  - Part of Automatic Repeat reQuest (ARQ).
  - Disadvantage: Inefficient for high bandwidth/delay networks.
2. Sliding Window Protocols:
  - One-Bit Sliding Window: Stop-and-Wait with window size 1.
  - Go-Back-N:
    - Window size > 1; sender retransmits all frames after an error.
    - Useful for high bandwidth-delay products.
  - Selective Repeat: Retransmits only erroneous frames (more efficient).

5. 多重访问协议（Multiple-Access Protocols）

多个设备共享同一通信信道时，需要使用多重访问协议来调度信道的使用：

Purpose: Manage access to a shared communication channel.
Categories:
1. Channelization Protocols:
  - 把信道“分片”，每人固定用一部分
  - FDMA (Frequency-Division Multiple Access): Divides bandwidth by frequency.
    - 每个设备用不同频率传输 → 类似收音机不同频道
  - TDMA (Time-Division Multiple Access): Divides bandwidth by time slots.
    - 时间分片，每个设备轮流用 → 类似考试按顺序上场
  - CDMA (Code-Division Multiple Access): Uses unique codes for each station.
    - 每个用户用不同“密码”编码传输 → 类似用不同语言讲话，能分辨开
2. Random Access (Contention-Based) Protocols:
  - 谁都可以抢着发，冲突了就重发
  - Aloha: Transmit anytime; retransmit on collision.
    - 原始方法：想发就发 → 冲突后等随机时间重发
  - Slotted Aloha: Transmit only at slot start; reduces collision probability.
    - 时隙版（Slotted ALOHA）将时间分片，提升效率
  - CSMA (Carrier Sense Multiple Access):
    - 先“听”信道有没有人在用，没人用再发
    - Persistent: Sense channel; transmit when idle.
    - Non-Persistent: Wait random time if busy, then retry.
  - CSMA/CD: 以太网用的，边发边听，撞了就停
  - CSMA/CA: 无线网络用的，尽量避免碰撞
3. Controlled Access (Collision-Free) Protocols:
  - 有人“安排顺序”，轮到谁谁发
  - Polling: Master node controls transmission order.
    - 中央控制器轮流问每个设备：“你有没有要发的？”
  - Token-Passing: Token holder transmits; passes token when done.
    - 一个“令牌”在网络中轮流传递，拿到令牌才能发数据
  - Reservation

6. 扩频技术（Spread Spectrum）

扩频技术用于减少干扰并提高通信安全性，常见的扩频方式有：

6.1 跳频扩频 Frequency-Hopping Spread Spectrum (FHSS)

原理：信号在多个频率之间跳跃，避免干扰和窃听。
- Hops between frequencies using a spreading code.
- Receiver syncs with transmitter to recover data.
优点：提高抗干扰能力和安全性。

6.2 直接序列扩频 Direct Sequence Spread Spectrum (DSSS)

原理：通过使用扩频码将信号扩展到更宽的频带，提高抗干扰能力。
- Spreads signal across a wider band using a spreading code.
- XORs data with code for transmission; reverses for reception.
优点：减少信号衰减和干扰。

Quick Reference Table

Technique	Purpose	Key Feature	Pros	Cons
Framing (Bit Stuffing)	Frame delineation	Inserts 0 after five 1s	Reliable boundary	Overhead
CRC	Error detection	Polynomial division	Detects burst errors	No correction
Hamming Code	Error correction	Check bits at 2^n positions	Corrects single errors	Limited to single bits
Stop-and-Wait	Flow control	Waits for ACK	Simple	Low efficiency
Go-Back-N	Flow control	Retransmits all after error	Handles high bandwidth	Wasteful retransmission
CSMA/CD	Channel access	Collision detection	Reduces collision time	Requires hardware
Token-Passing	Collision-free access	Token controls transmission	No collisions	Token overhead

Chapter 4: Network and Transport Layers

Overview

Purpose: The Network Layer handles logical addressing and routing of packets across networks, while the Transport Layer ensures end-to-end communication, reliability, and flow control.
Key Topics:
1. IP Addressing (IPv4 and IPv6)
2. Network Routing
3. Transport Protocols (TCP and UDP)
4. Congestion Control
5. Quality of Service (QoS)

1. IP Addressing

IP Addressing
- IP address: 32-bit identifier associated with each host or router interface
- interface: connection between host/router and physical link
  - router’s typically have multiple interfaces
  - host typically has one or two interfaces (e.g., wired Ethernet, wireless 802.11)
  - Interface 是物理或逻辑网络连接点，用来收发 IP 数据包，属于网络层概念。
Subnets
- What’s a subnet ?
  - device interfaces that can physically reach each other without passing through an intervening router
- IP addresses have structure:
  - subnet part: devices in same subnet have common high order bits
  - host part: remaining low order bits
- Recipe for defining subnets：
  - detach each interface from its host or router, creating “islands” of isolated networks
  - each isolated network is called a subnet

IPv4

Structure: 32-bit address, written in dotted decimal (e.g., 158.182.7.1).
Header: 20-byte fixed part + optional variable part.
- Fields: Version (4), IHL (header length), Type of Service (ToS), Total Length, Identification, Flags (DF, MF), Fragment Offset, Time-to-Live (TTL), Protocol, Header Checksum, Source/Destination Addresses.
Classful Addressing: Divided into five classes (A-E).
Subnetting: Splits networks using subnet masks.
Private Addresses: Uses NAT (Network Address Translation) to map private IPs (e.g., 10.0.0.0) to public IPs.

IPv6

Structure: 128-bit address, written as eight groups of four hexadecimal digits (e.g., 8000:0000:89AB:CDEF:8000:0000:89AB:CDEF).
Header: 40-byte fixed header.
- Fields: Version (6), Traffic Class, Flow Label, Payload Length, Next Header, Hop Limit, Source/Destination Addresses.
Advantages: Larger address space, better QoS, no fragmentation by routers.
Transition from IPv4:
- Dual Stack: Supports both IPv4 and IPv6. 在同一台设备上同时运行 IPv4 和 IPv6 协议栈，使其能够处理这两种协议的数据包。
- Tunneling: Encapsulates IPv6 packets in IPv4. 通过在 IPv4 网络中“封装”IPv6 数据包，使其可以在不支持 IPv6 的网络上传输。常见技术有 6to4、Teredo、ISATAP 等。
- Header Translation: Converts between formats. 直接将 IPv6 报文转换为 IPv4 报文（或反之），以便在 IPv4-only 或 IPv6-only 网络中通信。常用协议如 NAT64、DNS64 等。

策略	优点	缺点	使用场景
Dual Stack	高兼容性，适用于渐进过渡	成本高，管理复杂	IPv4 与 IPv6 并存环境
Tunneling	利用现有IPv4基础设施传输IPv6流量	性能低，排障难	IPv6 被 IPv4 网络隔离的情况
Header Translation	实现 IPv4 和 IPv6 互通	转换复杂，可能导致兼容性问题	IPv6-only 网络访问 IPv4 服务

2. Network Routing

Delivery

Direct Delivery: Packet sent within the same network.
Indirect Delivery: Packet routed through multiple networks.
Forwarding: Uses routing tables to determine the next hop.

Routing Algorithms

Shortest Path Routing (Dijkstra Algorithm):
- Finds the shortest path using a graph (nodes = routers, edges = links).
- Steps: Set initial node to 0, others to infinity; update tentative distances; mark nodes as visited; repeat until done.
Flooding:
- Sends packets on all outgoing lines except the incoming one.
- Uses hop counter to limit duplicates.
Distance Vector Routing:
- Each router maintains a table of distances to destinations, updated via neighbor exchanges.
- Issue: Count-to-Infinity problem (slow to adapt to bad news).
Link State Routing:
- Routers flood link state packets (neighbors, costs); each builds a subnet graph to compute routes.
- Steps: Learn neighbors, measure line costs, build/distribute packets, compute routes.

Special Routing

Broadcast: Sends to all destinations (e.g., flooding).
Multicast: Sends to a group (via unicast emulation or router destination lists).
Hierarchical Routing: Divides routers into regions for scalability.

3. Transport Layer

TCP (Transport Control Protocol)

Type: Connection-oriented, reliable.
Operation:
- Sender starts a timer with each segment; retransmits if timeout occurs.
- Receiver acknowledges the next expected sequence number.
TCP Segment Header: Source/Destination Ports, Sequence/Acknowledgment Numbers, Header Length, Flags (e.g., FIN), Window Size, Checksum, Options.
- 源端口号和目的端口号：用于标识连接的本地端点（即是哪两个应用在通信）。
- 序列号（Sequence Number）和确认号（Acknowledgement Number）：用于实现可靠传输，确保数据按序到达并被确认。
- TCP 首部长度：指出首部中包含了多少个 32 位字（即 4 字节单位）。
- 六个 1 位标志位（Flags）：用于控制连接状态和数据传输行为（如 SYN、ACK、FIN 等）。
- 窗口大小（Window Size）：告知对方从已确认的字节开始，最多还能接收多少字节的数据（用于流量控制）。
- 校验和（Checksum）：用于检验 TCP 首部和数据部分是否在传输过程中出现错误。
- 选项字段（Options）：用于扩展 TCP 首部的功能，比如窗口扩大、时间戳等。
Connection:
- Establishment: Three-way handshake.
- Release: FIN bit set by either party.
Timer Management
- For each connection, TCP maintains the timeout interval as:
- $$Timeout = \mu + 4 \delta$$
- Where
  - $\mu$ is the mean round-trip time (RTT) of the observations
  - $\delta$ is the standard deviation of the observations
- TCP constantly adjusts the timeout interval based on continuous measurements of network performance.

UDP (`User Datagram Protocol`)

Type: Connectionless, unreliable.
Header: 8 bytes (Source/Destination Ports, Length, Checksum).
Use: Simple, low-overhead applications (e.g., DNS, streaming).

4. `Congestion Control`

Basics

Definition: Techniques to prevent or remove network congestion when load exceeds capacity.
Categories:
- Open-Loop: Preventive (e.g., traffic shaping).
- Closed-Loop: Reactive (e.g., backpressure, choke packets).

Mechanisms

TCP Congestion Control:
- Window size grows exponentially until a threshold (initially 64 KB), then linearly.
- On timeout, threshold halves, and window resets to one.
Load Shedding:
- Routers discard packets when overloaded (randomly or via RED algorithm).
- RED (Random Early Detection): Drops packets before severe congestion based on queue length.
Metrics Used to Monitor a Subnet for Congestion
- Percentage of all packets discarded for lack of buffer space; 有多少数据包因为路由器“排不下”而被丢弃。
- Average of queue lengths; 排在路由器队列里等待转发的数据包数量的平均值。
- Number of packets that time out and are retransmitted; 因为迟迟没收到确认，认为丢了而再次发送的包数量。
- Average packet delay; 数据包从发送到接收所需的平均时间。
- Standard deviation of packet delay, etc. 用于衡量网络延迟的稳定性，大波动代表网络不稳。

Data Traffic

Focus: Congestion control avoids traffic jams; QoS ensures suitable conditions.
Profiles: Bursty, steady, or variable traffic.

5. Quality of Service (QoS)

Requirements

Varies by application:
- E-mail: High reliability, low delay/bandwidth.
- Video on Demand: Low reliability, high jitter/bandwidth.
- Telephony: Low reliability, high delay/jitter.

Techniques

Buffering: Reduces jitter (non-real-time only).
Traffic Shaping: Smooths traffic flow.
Resource Reservation: Allocates bandwidth.
Admission Control: Limits new connections.

Jitter Control

Definition: Variation in packet arrival times.
Solution: Buffering for non-real-time apps (e.g., video-on-demand).

Key Concepts

Packet Encapsulation: Layers add headers (e.g., Ethernet, IP, UDP, RTP for multimedia).
Network Layer: Logical addressing, routing.
Transport Layer: End-to-end delivery, reliability.

Quick Reference Table

Topic	Key Feature	Examples/Uses	Pros	Cons
IPv4	32-bit, 20-byte header	Internet, LANs	Widely used	Limited address space
IPv6	128-bit, 40-byte header	Next-gen Internet	Vast address space, QoS	Transition complexity
Dijkstra Algorithm	Shortest path via graph	Routing	Optimal paths	Computationally intensive
Distance Vector	Distance tables, neighbor updates	RIP protocol	Simple	Slow to bad news
TCP	Reliable, connection-oriented	HTTP, FTP	Ensures delivery	High overhead
UDP	Connectionless, 8-byte header	DNS, streaming	Fast, low overhead	No reliability
Congestion Control	Manages network load	TCP, RED	Prevents collapse	May drop packets
QoS	Ensures service levels	Video, telephony	Meets app needs	Resource-intensive

Chapter 5: Network Programming

一、应用程序接口（API）与网络编程

API（Application Programming Interface）：向上提供简化接口，隐藏底层复杂性
在网络编程中，Socket API 是连接应用层与传输层（TCP/UDP）的桥梁

二、Socket 套接字概念

套接字（Socket）：
- 组成：
  - an internet address
  - an end-to-end protocol (e.g. TCP or UDP)
  - a port number
- 应用程序进程间的“端点”
- 由 IP 地址 + 端口号唯一标识
- 分为流式（TCP）和数据报（UDP）两类
Socket 的作用：
- 发送/接收数据
- 支持同主机或跨主机进程通信

三、客户端-服务器模型

服务器端（Server）：
- 创建“被动套接字”并绑定端口，调用 listen() 等待连接
- accept() 建立每个客户端连接
客户端（Client）：
- 创建“主动套接字”，调用 connect() 发起连接
- 知晓服务器 IP + 端口

四、TCP 通信基本函数（面向连接）

步骤	函数	说明
初始化（Win）	`WSAStartup()`	加载 Winsock 库
创建套接字	`socket()`	`AF_INET, SOCK_STREAM, 0`
绑定端口	`bind()`	服务器常用，绑定本地地址与端口
监听	`listen()`	将套接字置为被动监听状态
接受连接	`accept()`	返回新的通信套接字
建立连接	`connect()`	客户端调用，连接到服务器
发送数据	`send()`	阻塞/非阻塞发送字节流
接收数据	`recv()`	接收对端发送的字节流；返回 0 表示对端关闭
关闭套接字	`closesocket()`/`close()`	释放资源
清理（Win）	`WSACleanup()`	卸载 Winsock 库

五、UDP 通信基本函数（无连接）

步骤	函数	说明
创建套接字	`socket(AF_INET, SOCK_DGRAM, 0)`	UDP 模式
绑定端口	`bind()`	服务器接收时使用
发送数据	`sendto()`	指定目标地址、端口发送数据
接收数据	`recvfrom()`	获取发送方地址与数据
关闭套接字	`closesocket()`/`close()`	释放资源

六、常用辅助函数

地址解析
- gethostbyname(hostname) → struct hostent*
- gethostbyaddr(addr, len, type) → 反向域名解析
套接字选项
- setsockopt(sock, level, optname, &optval, optlen)
  - 例：SO_REUSEADDR 端口重用
字节序转换
- 网络字节（大端） ↔ 主机字节（小端）
- htons() / htonl() / ntohs() / ntohl()

七、多客户端并发处理

线程模型：为每个 accept 出来的套接字创建新线程/进程
事件驱动：使用 select()、poll() 或 I/O 多路复用

八、示例代码结构概览

TCP 服务器端（Server）

#include <stdio.h>
#include <winsock2.h>

int main() {
    WSADATA wsaData;
    SOCKET serverSocket, clientSocket;
    struct sockaddr_in serverAddr, clientAddr;
    int addrLen = sizeof(clientAddr);
    char buffer[1024];

    // 初始化 Winsock 库
    WSAStartup(MAKEWORD(2, 2), &wsaData);

    // 创建 TCP socket
    serverSocket = socket(AF_INET, SOCK_STREAM, 0);

    // 配置服务器地址结构体
    serverAddr.sin_family = AF_INET;             // IPv4
    serverAddr.sin_port = htons(8888);           // 端口 8888
    serverAddr.sin_addr.s_addr = INADDR_ANY;     // 本机所有 IP

    // 绑定地址与端口
    bind(serverSocket, (SOCKADDR*)&serverAddr, sizeof(serverAddr));

    // 监听连接请求
    listen(serverSocket, 5);
    printf("服务器已启动，等待连接...\n");

    // 接受客户端连接
    clientSocket = accept(serverSocket, (SOCKADDR*)&clientAddr, &addrLen);
    printf("客户端已连接！\n");

    // 接收数据
    recv(clientSocket, buffer, sizeof(buffer), 0);
    printf("客户端发来: %s\n", buffer);

    // 发送回应
    send(clientSocket, "Hello, Client!", strlen("Hello, Client!") + 1, 0);

    // 关闭套接字
    closesocket(clientSocket);
    closesocket(serverSocket);
    WSACleanup();
    return 0;
}

TCP 客户端（Client）

#include <stdio.h>
#include <winsock2.h>

int main() {
    WSADATA wsaData;
    SOCKET clientSocket;
    struct sockaddr_in serverAddr;
    char buffer[1024] = "Hello, Server!";

    WSAStartup(MAKEWORD(2, 2), &wsaData);

    // 创建 socket
    clientSocket = socket(AF_INET, SOCK_STREAM, 0);

    // 设定服务器地址信息
    serverAddr.sin_family = AF_INET;
    serverAddr.sin_port = htons(8888);
    serverAddr.sin_addr.s_addr = inet_addr("127.0.0.1");  // 本地地址

    // 连接服务器
    connect(clientSocket, (SOCKADDR*)&serverAddr, sizeof(serverAddr));

    // 发送数据
    send(clientSocket, buffer, strlen(buffer) + 1, 0);

    // 接收服务器回应
    recv(clientSocket, buffer, sizeof(buffer), 0);
    printf("服务器回复: %s\n", buffer);

    // 关闭连接
    closesocket(clientSocket);
    WSACleanup();
    return 0;
}

UDP 服务器代码

#include <stdio.h>
#include <winsock2.h>

int main() {
    WSADATA wsaData;
    SOCKET udpSocket;
    struct sockaddr_in serverAddr, clientAddr;
    int addrLen = sizeof(clientAddr);
    char buffer[1024];

    WSAStartup(MAKEWORD(2, 2), &wsaData);

    udpSocket = socket(AF_INET, SOCK_DGRAM, 0);  // 创建 UDP socket

    serverAddr.sin_family = AF_INET;
    serverAddr.sin_port = htons(9999);
    serverAddr.sin_addr.s_addr = INADDR_ANY;

    bind(udpSocket, (SOCKADDR*)&serverAddr, sizeof(serverAddr));
    printf("UDP服务器已启动，等待消息...\n");

    recvfrom(udpSocket, buffer, sizeof(buffer), 0, (SOCKADDR*)&clientAddr, &addrLen);
    printf("接收到客户端消息: %s\n", buffer);

    sendto(udpSocket, "UDP 回复成功", strlen("UDP 回复成功") + 1, 0,
           (SOCKADDR*)&clientAddr, addrLen);

    closesocket(udpSocket);
    WSACleanup();
    return 0;
}

UDP 客户端

#include <stdio.h>
#include <winsock2.h>

int main() {
    WSADATA wsaData;
    SOCKET udpSocket;
    struct sockaddr_in serverAddr;
    int addrLen = sizeof(serverAddr);
    char buffer[1024] = "Hello UDP Server!";

    WSAStartup(MAKEWORD(2, 2), &wsaData);

    udpSocket = socket(AF_INET, SOCK_DGRAM, 0);

    serverAddr.sin_family = AF_INET;
    serverAddr.sin_port = htons(9999);
    serverAddr.sin_addr.s_addr = inet_addr("127.0.0.1");

    sendto(udpSocket, buffer, strlen(buffer) + 1, 0,
           (SOCKADDR*)&serverAddr, addrLen);

    recvfrom(udpSocket, buffer, sizeof(buffer), 0, (SOCKADDR*)&serverAddr, &addrLen);
    printf("服务器回应: %s\n", buffer);

    closesocket(udpSocket);
    WSACleanup();
    return 0;
}

Chapter 6: Ethernet and Wireless Networks

1. IEEE Project 802 & LAN Standards

Initiated in 1985 by IEEE to standardize LAN protocols across manufacturers.
Focuses on defining standards for Physical and Data Link Layers.
Key standards:
- IEEE 802.3 → Ethernet
- IEEE 802.5 → Token Ring
- IEEE 802.11 → Wireless LAN (Wi-Fi)
- IEEE 802.15 → Bluetooth

2. Ethernet (IEEE 802.3)

The original Ethernet was created in 1976 at Xerox’s Palo Alto Research Center (PARC).

Frame Format

Preamble (7 bytes): Synchronization using 10101010 pattern.
Start Frame Delimiter (SFD): Indicates frame start.
Destination/Source Address (6 bytes each): MAC addresses.
Type: Indicates upper-layer protocol (e.g., IP, ARP).
Data: Up to 1500 bytes.
Pad: Fills frame if data is < 46 bytes.
CRC: Error detection.

Frame Size

Minimum: 64 bytes
Maximum: 1518 bytes (including CRC)

Important

How to Determine the Minimum Ethernet Frame Size?
Ethernet uses CSMA/CD (Carrier Sense Multiple Access with Collision Detection). To detect collisions while transmitting, a frame must be “long enough” to still be transmitting when a collision occurs.

Formula:
$$
\text{Minimum frame size} = 2 \times \text{maximum propagation delay} \times \text{transmission rate}
$$

Why?

If a station finishes transmitting before it hears a collision, it cannot detect it → collision undetected

The frame must be at least long enough to keep the transmitter active until a signal can reach the farthest end and back

Standard Ethernet Example:

Max cable length: 2500 m (10 Mbps coaxial Ethernet)

Propagation delay: ~25 μs one way ⇒ 50 μs round trip

Transmission rate: 10 Mbps

$$
\text{Minimum frame size} = 10^7 \times 50 \times 10^{-6} = 500 \text{ bits} = 64 \text{ bytes}
$$

Thus, the minimum Ethernet frame size is standardized as 64 bytes, including headers and CRC.

Address Types

Unicast: LSB of first byte = 0
Multicast: LSB of first byte = 1
Broadcast: All 1s (FF:FF:FF:FF:FF:FF)

3. Ethernet Evolution

Fast Ethernet (IEEE 802.3u)

100 Mbps
Backward-compatible with standard Ethernet
Encoding: 4B/5B, NRZ-I

Gigabit Ethernet (IEEE 802.3z)

1000 Mbps
Encoding: 8B/10B
Uses fiber or copper

10/40/100 Gigabit Ethernet

Standardized by IEEE 802.3ba (2010)
Used in data centers and high-speed backbones

4. Manchester Encoding (Used in Ethernet)

Each bit has a transition:
- 1: High to low
- 0: Low to high
Provides synchronization between sender and receiver.

5. Ethernet MAC Protocol: CSMA/CD

Carrier Sense Multiple Access with Collision Detection

Carrier Sense: Listen before transmitting.
Transmit if idle.
Detect collision while transmitting.
If collision → Send jam signal → Back off → Retry

Back-off Strategy: Binary Exponential Backoff

Wait time increases exponentially after each collision.
Max retry attempts = 16 (then give up).

Important

Binary Exponential Back-off Algorithm (Expanded)
After a collision, Ethernet does not retry immediately. Instead, it waits a random time before attempting to resend. The waiting time increases exponentially with the number of attempts.

Key Steps:

After the 1st collision, wait for a random time between 0 and 1 slot time

After the 2nd collision, wait for 0–3 slot times

After the 3rd collision, wait for 0–7 slot times

…

After the kth collision (k ≤ 10), wait randomly in the range 0–(2^k – 1) slots

After 10 collisions, the range freezes at 0–1023

If 16 collisions occur → give up and report transmission failure

Slot time (for 10 Mbps Ethernet):

One slot time = 512 bits = 64 bytes = 51.2 μs

Purpose:

Avoid repeated collisions by spreading retransmissions over increasing time intervals

Improve efficiency under heavy load

Example Scenario:
After 3 collisions, a device randomly chooses a wait time between:
$$
0 \text{ to } 2^3 - 1 = 0 \text{ to } 7 \text{ slot times}
$$

If one slot = 51.2 μs, it could wait:
$$
0 \text{ to } 358.4 \mu s
$$

6. Token Ring (IEEE 802.5)

Uses a circulating token for access control.
A station must possess the token to transmit.
Frames:
- Token: Small control frame
- Data/Command Frames
Includes a priority system and an active monitor for fault management.

7. LAN Devices: Hub, Bridge, Switch, Router

Device	Layer	Function
Hub	1	Signal repeater, broadcasts to all ports
Bridge	2	Filters and forwards based on MAC address
Switch	2	Multi-port bridge, full-duplex, isolates traffic
Router	3	Uses IP address for packet forwarding

Compare Hub, Bridge, Switch, and Router

Hub operates at the Physical Layer (Layer 1).
It simply broadcasts incoming signals to all ports without any filtering. It cannot distinguish devices.

Bridge works at the Data Link Layer (Layer 2).
It filters and forwards traffic based on MAC addresses and separates collision domains.

Switch is an advanced multi-port Bridge also at Layer 2.
It learns MAC addresses and forwards frames only to the correct destination port, improving efficiency.

Router operates at the Network Layer (Layer 3).
It uses IP addresses to route packets between different networks or subnets, and separates broadcast domains.

8. `Wireless LANs` (IEEE 802.11 - Wi-Fi)

Frequencies and Channels

Operates in the 2.4 GHz ISM band
Common standards:
- 802.11b: 11 Mbps
- 802.11g: 54 Mbps
- 802.11n: 600 Mbps

Network Structure

Basic Service Set (BSS):
- With AP: Infrastructure mode
- Without AP: Ad hoc mode
Extended Service Set (ESS): Multiple BSSs connected

Important (distinguish)

什么是 BSS？
BSS（Basic Service Set） 是无线局域网（WLAN）中的最小网络单位，表示一组可以彼此通信的无线设备（Stations, STA）。
每个 BSS 都由一个唯一的 ID 标识：BSSID（通常就是 AP 的 MAC 地址）

两种 BSS 类型对比：

类型 有 AP 的 BSS 没有 AP 的 BSS

正式名称 Infrastructure BSS（基础架构模式） Independent BSS（IBSS，自组织模式）

是否有 AP（接入点）有，AP 管理整个 BSS 没有，所有节点平等通信

通信方式所有设备必须通过 AP 中转 STA 之间可直接通信（点对点）

是否连接互联网可以（AP 接入有线网）不能（除非某个 STA 连接外部网络）

BSSID 是谁的地址？ AP 的 MAC 地址由发起者 STA 动态生成一个临时地址

应用场景常见于家庭、公司、校园 Wi-Fi 例如临时会议文件共享、战术通信、蓝牙热点等

能否扩展为 ESS？可以，与多个 AP 组成 ESS 网络不能（无中心节点）

类型	有 AP 的 BSS	没有 AP 的 BSS
正式名称	Infrastructure BSS（基础架构模式）	Independent BSS（IBSS，自组织模式）
是否有 AP（接入点）	有，AP 管理整个 BSS	没有，所有节点平等通信
通信方式	所有设备必须通过 AP 中转	STA 之间可直接通信（点对点）
是否连接互联网	可以（AP 接入有线网）	不能（除非某个 STA 连接外部网络）
BSSID 是谁的地址？	AP 的 MAC 地址	由发起者 STA 动态生成一个临时地址
应用场景	常见于家庭、公司、校园 Wi-Fi	例如临时会议文件共享、战术通信、蓝牙热点等
能否扩展为 ESS？	可以，与多个 AP 组成 ESS 网络	不能（无中心节点）

MAC Layer Protocol: CSMA/CA (Collision Avoidance)

802.11 supports CSMA/CA (CSMA with collision avoidance) for MAC protocol.

Why not CSMA/CD? Wireless cannot detect collisions reliably due to:
- Hidden station problem
- Exposed station problem

CSMA/CA Steps

Station A sends RTS to B
B replies CTS
A sends data frame
B replies ACK
Nearby nodes reserve channel using NAV (Network Allocation Vector)

9. Point Coordination Function (PCF) – Optional in 802.11

AP polls stations instead of random access.
Avoids collisions but adds complexity.

10. Bluetooth (IEEE 802.15)

Characteristics

Short-range (10–100 meters), low power, low cost
Operates in 2.4 GHz ISM band
Data rates: 1–24 Mbps

Topologies

Piconet: 1 master + up to 7 active slaves
Scatternet: Multiple interconnected piconets

11. Summary Comparison Table

Feature	Ethernet (802.3)	Wi-Fi (802.11)	Bluetooth (802.15)
Medium	Wired	Wireless	Wireless
Access Method	CSMA/CD	CSMA/CA	Polling (master–slave)
Max Data Rate	10–100 Gbps	Up to 600 Mbps	Up to 24 Mbps
Range	~100 m	~100 m	~10–100 m
Topology	Star / Bus	Star (via AP)	Piconet/Scatternet
Frequency Band	N/A	2.4 / 5 GHz	2.4 GHz

Lecture Notes: Data Communications and Networking

https://tosakaucw.github.io/lecture-notes-data-communications-and-networking/

Author

TosakaUCW

Posted on

2025-03-25

Updated on

2025-05-27

Lecture Notes: Data Communications and Networking

Chapter 1: Basic Concepts

1. Introduction to Data Communications

What is Data Communication?

Five Key Components:

2. Network Protocols

3. Data Flow Types

4. Analog vs. Digital Signals

Analog:

Digital:

5. Digital Encoding Schemes

Non-Return-to-Zero (NRZ):

Manchester:

4B/5B Encoding:

6. Analog Signal Transmission of Digital Data

Amplitude Modulation (AM):

Frequency Modulation (FM):

Phase Modulation (PM):

7. Converting Analog to Digital – PCM

8. Channel Capacity Theorems

Nyquist Theorem:

Shannon’s Theorem:

9. Computer Networks

What is a Network?

Network Categories:

10. Network Topologies

Bus

Ring

Star

Tree

Mesh

11. Network Software & Protocol Hierarchies

Why Layering?

Design Issues:

12. Connection-Oriented vs Connectionless Services

Connection-Oriented:

Connectionless:

13. Service Primitives (APIs for Communication)

14. Reference Models

OSI Model – 7 Layers

TCP/IP Model (More practical)

15. Information Flow in TCP/IP Model

Chapter 2: Physical Layer

1. Overview of the Physical Layer

2. Fourier Analysis in Communications

What is Fourier Analysis?

Why is Fourier Analysis important?

Key Terms:

3. Transmission Media

Categories of Transmission Media:

A. Guided Media (have physical path)

B. Unguided Media (no physical path)

4. Guided Transmission Media

A. Twisted-Pair Cable

B. Coaxial Cable

C. Fiber Optic Cable

5. Unguided Transmission Media (Wireless)

Characteristics:

Two common encoding techniques:

6. Electromagnetic Spectrum

7. Wireless Propagation Methods

A. Omnidirectional Propagation

B. Unidirectional Propagation

8. Types of Wireless Transmission

A. Radio Transmission

B. Microwave Transmission

C. Infrared Transmission

D. Lightwave Transmission

9. Communication Satellites

考点精选

Chapter 3: Data Link Layer

1. Overview

2. Framing

3. Error Control

Error Detection

Error Correction

4. Flow Control

5. 多重访问协议（Multiple-Access Protocols）

6. 扩频技术（Spread Spectrum）

6.1 跳频扩频 Frequency-Hopping Spread Spectrum (FHSS)

`Five Key Components`:

3. `Data Flow Types`

5. `Digital Encoding Schemes`

`Non-Return-to-Zero (NRZ)`:

`Manchester`:

`4B/5B Encoding`:

8. `Channel Capacity Theorems`

`Nyquist Theorem`:

`Shannon’s Theorem`:

10. `Network Topologies`

`Bus`

`Ring`

`Star`

`Tree`

`Mesh`

14. `Reference Models`

`Why is Fourier Analysis important?`

`Categories of Transmission Media`:

A. `Guided Media` (have physical path)

7. `Wireless Propagation Methods`

2. `Framing`

3. `Error Control`

4. `Flow Control`

UDP (`User Datagram Protocol`)

4. `Congestion Control`

8. `Wireless LANs` (IEEE 802.11 - Wi-Fi)