Latex 相关记录

• 编译方式
• 页眉页脚
  • Latex 预定义页面风格
  • 自定义页面风格
• 目录
• 参考文献
• 附录
• 代码块
  • 一般情况
  • 只插python
• 图片
  • 多个图片并排
• 表格
  • 多个表格并排放置
  • 合并单元格
  • 单元格内换行
• 列表
  • 有编号列表
  • 无编号列表
• 公式
  • 大括号
  • 矩阵
• 杂七杂八
  • 使用英文标签

编译方式

改为用 xelatex 编译。
放在导言栏最前面。

1

%!TEX program = xelatex

页眉页脚

Latex 预定义页面风格

• empty：没有页眉页脚。
  • 在标题页（包括手动或者自动由 \maketitle 生成的 titlepage 环境），会使用该风格禁用所有页眉页脚。
• plain：没有页眉，页脚是居中的页码。
  • report 和 article 默认使用该风格。
  • 不单独成页的 \maketitle，单独成页的 \part，以及 \chapter 所在的一页，自动使用该风格。
• heading：没有页脚，页眉是章节名称的页码。
  • book 默认使用该风格。
• myheading：没有页脚，页眉是章节名称的页码。

自定义页面风格

调用 fancyhdr 宏包。

1
2
3

\usepackage{fancyhdr} %设置全文页眉、页脚的格式
\pagestyle{fancy}
\hypersetup{colorlinks=true,linkcolor=black}% 去除引用红框，改变颜色

使用 \fancypagestyle{stylename}{} 的形式设置不同的页眉页脚风格。

1
2
3
4
5
6
7
8
9
10

\fancypagestyle{mainFancy} % 正文部分格式
{
  \fancyhf{} 
  \renewcommand\headrulewidth{.5pt}  % 页眉横线
  \renewcommand\footrulewidth{0pt}
    
  \fancyhead[L]{Team \# 2403961} % 页眉左侧
  \fancyhead[R]{Page \thepage\ of 25} % 页眉右侧
  \fancyfoot{}
}

其中常见的指令有

• \fancyhf{}：通常只用于清空页眉页脚。
• \fancyhead[]{}：设置页眉，中括号内为命令参数，没有参数时可省去；大括号内为内容，为空则表示清空页眉。
• \fancyfoot[]{}：设置页脚。

上述指令可选参数如下

参数可组合使用，如 \fancyhead[OR, EL]{\thepage}，表示在奇数页左侧、偶数页右侧页眉显示当前页数。

上述设置均在导言栏中完成，在正文中切换页眉风格时需使用 \pagestyle{stylename}。
也可以用 \thispagestyle{} 单独设置当前页的风格。

目录

生成目录

1
2

\renewcommand*\contentsname{\hfill Contents \hfill} % 使目录居中
\tableofcontents

将参考文献添加到目录中

1

\addcontentsline{toc}{section}{Reference} 

将附录添加到目录中

1

\addappheadtotoc

参考文献

引用宏包

1
2

\usepackage{bibentry}
\usepackage[square, comma, sort&compress, numbers]{natbib}

如果直接 \usepackage{natbib}，使用时可能会报错：Bibliography not compatible with author-year citations.

在正文中使用

1
2
3
4

\begin{thebibliography}{99} % {}内表示序号最大位数（两位）
  \bibitem{ref1}This is the first ref.
  \bibitem{ref2}This is the second ref.
\end{thebibliography}

附录

引用宏包

1

\usepackage{appendix}

在正文中使用

1
2
3
4
5

\begin{appendices}
\section*{Appendices}
This is appendices.

\end{appendices}

不知道为什么，如果不加 \section*{Appendices}，附录部分不会显示一个 Appendices 的标题。

代码块

一般情况

导言栏

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

\usepackage{color}
\usepackage{listings}
\lstset
{ 
  language=C, % 设置语言
  basicstyle=\footnotesize, % 代码字体    
  numbers=left, % 行编号位置
  numberstyle=\footnotesize, % 标号字体
  stepnumber=1, % 表示每行都标号      
  numbersep=7pt, % 标号离代码框的距离                
  backgroundcolor=\color{white}, % 背景颜色
  showspaces=false,               
  showstringspaces=false,       
  showtabs=false,                  
  frame=single,           
  tabsize=2, % 一个Tab等于的空格数       
  captionpos=b,          
  breaklines=true,       
  breakatwhitespace=false,    
  escapeinside={\%*}{*}   
}      

正文使用

1
2
3
4
5
6
7
8
9

\begin{lstlisting}
  // hello?
  int main()
  {
    printf("hello");

    return 0;
  }
\end{lstlisting}

只插python

导言栏

1

\usepackage{pythonhighlight}

正文使用

1
2
3
4

\begin{python}
  # hello? 
  print("hello")
\end{python}

图片

在导言栏指定图片的存放位置，后续引用的图片都需要存储在该文件夹中，该文件夹与 tex 文件在同一级目录中。

1

\graphicspath {{images/}} % 存放图片的文件夹

在正文中使用

1
2
3
4
5

\begin{figure}[H]
  \centering
  \includegraphics[width=0.43\linewidth]{image1.png} % 设置图片大小和指定插入的图片
  \caption{image1} % 设置图片标题
\end{figure}

多个图片并排

使用 minipage 实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

\begin{figure}[H]
	\centering
	\begin{minipage}[H]{0.45\linewidth} % 设置 minipage 的大小
    \centering
    \includegraphics[width=0.9\linewidth]{image1.png}
    \caption{image1}
  \end{minipage}
  % 调整两个 minipage 间距
  \hspace{0cm}
  \centering
  \begin{minipage}[H]{0.45\linewidth}
    \centering
    \includegraphics[width=0.9\linewidth]{image2.png}   
    \caption{image2}
  \end{minipage}
\end{figure}

\hfill%：放在两个 minipage 中间，使图片的分布撑满整行。

表格

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

\begin{table}[H]
  \centering % 表格居中
  \setlength{\tabcolsep}{8mm}
  \begin{tabular}{c|c|c}
      \hline
      
      \hline
      A & B & C \\
      \hline
      
      \hline
      a1 & b1 & c1 \\
      \hline
      a2 & b2 & c2 \\
      \hline
      a3 & b3 & c3 \\

      \hline
      
      \hline
  \end{tabular}
  \caption{a table} % 设置表格标题
\end{table}

\begin{tabular}{c|c|c}

• 对齐方式
  • c：居中对齐
  • l：左对齐
  • r：右对齐
• 列数
  有几个字母就有几列，每一列的对齐方式可以单独设置
• 列分隔线
  有 | 的地方就有列分隔线

\hline

• 画整行的分隔线，画两次可以起到加深的作用。
• 如果需要画指定格子的分隔线，可改为 \cline{2-3}，表示画第 2 格到第 3 格的行分隔线。

多个表格并排放置

使用 minipage 实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

\begin{center}
  % 第一个 minipage
  \begin{minipage}[H]{0.4\textwidth} % 设置 minipage 的大小
	  \centering
	  \begin{table}[H] % 第一个表格
      \centering
      \setlength{\tabcolsep}{8mm}
      \begin{tabular}{c|c|c}
          \hline
          
          \hline
          A & B & C \\
          \hline
          
          \hline
          a1 & b1 & c1 \\
          \hline
          a2 & b2 & c2 \\
          \hline
          a3 & b3 & c3 \\
          \hline
    
          \hline
          
          \hline
      \end{tabular}
      \caption{table 1}
    \end{table}
  \end{minipage}
  % 调整两个 minipage 间距
  \hspace{0cm}
  % 第二个 minipage
  \begin{minipage}[H]{0.4\textwidth}
    \centering
      \begin{table}[H]
        \centering 
        \setlength{\tabcolsep}{8mm}
        \begin{tabular}{c|c|c}
            \hline
            
            \hline
            A & B & C \\
            \hline
            
            \hline
            a1 & b1 & c1 \\
            \hline
            a2 & b2 & c2 \\
            \hline
            a3 & b3 & c3 \\
            \hline
            
            \hline
        \end{tabular}
        \caption{table 2}
      \end{table}
	\end{minipage}
\end{center}

图片和表格并排排列也是这样操作。

合并单元格

合并列：\multicolumn{cols}{pos}{text}

• cols：需要合并的列数
  
• pos：设置对齐方式和竖分隔线
  
• text：该单元格内容

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

\begin{table}[H]
  \centering
  \setlength{\tabcolsep}{8mm}
  \begin{tabular}{c|c|c}
      \hline
      
      \hline
      \multicolumn{3}{c}{A} \\ % 将三列合并成一列
      \hline
      
      \hline
      \multicolumn{2}{c|}{B} & C \\ % 将两列合并成一列
      \hline
      a1 & b1 & c1 \\
      \hline
      a2 & b2 & c2 \\
      \hline
      a3 & b3 & c3 \\

      \hline
      
      \hline
  \end{tabular}
  \caption{a table}
\end{table}

合并行：\multirow{rows}{width}{text}

• rows：需要合并的行数
• width：一般填 *
• text：单元格内容

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

\begin{table}[H]
  \centering
  \setlength{\tabcolsep}{8mm}
  \begin{tabular}{c|c|c}
      \hline
      
      \hline
      \multirow{2}{*}{A} & B & C \\ % 合并两行为一行
      \cline{2-3}
      ~ & b1 & c1 \\ % 被合并的单元格的内容需设置为 ~
      \hline
      a2 & b2 & c2 \\
      \hline
      a3 & b3 & c3 \\

      \hline
      
      \hline
  \end{tabular}
  \caption{a table}
\end{table}

单元格内换行

通过 \makecell 实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

\begin{table}[H]
  \centering
  \setlength{\tabcolsep}{8mm}
  \begin{tabular}{c|c|c}
      \hline
      
      \hline
      A & \makecell[c]{B1 \\ B2} & C \\ % B1 B2 为同一个单元格内换行显示
      \hline
      
      \hline
      a1 & b1 & c1 \\
      \hline
      a2 & b2 & c2 \\
      \hline
      a3 & b3 & c3 \\

      \hline
      
      \hline
  \end{tabular}
  \caption{a table}
\end{table}

列表

有编号列表

可以嵌套使用。

1
2
3
4
5
6
7
8
9

\begin{enumerate}
  \item one
  \begin{enumerate}
    \item one one
    \item one two
  \end{enumerate}
  \item two
  \item three
\end{enumerate}

无编号列表

可以嵌套使用。

1
2
3
4
5
6
7
8
9

\begin{itemize}
  \item one
  \begin{itemize}
    \item one one
    \item one two
  \end{itemize}
  \item two
  \item three
\end{itemize}

公式

equation：公式末尾会带有编号；多个公式在一个 equation 中时，一共只带有一个编号。

1
2
3
4
5
6
7
8
9
10
11

\begin{equation}% 单个公式
	A = B + C
\end{equation}

\begin{equation}
	\centering
	\begin{split} % 多个公式
		A_0 &= B + C \\ % & 表示对齐的位置
		C_0 &= B - C
	\end{split}
\end{equation}

align：多个公式时，每个公式结尾均带有编号。

1
2
3
4

\begin{align}
		A_0 & = A + B \\
		& = 3C
\end{align}

单个公式直接开数学环境打就行了，公式结尾不带编号

1
2
3
4
5
6
7

% 单独成行并居中
$$
A = B + C
$$

% 在行中间
所以 $A = B + C$

aligned：只能在数学环境中使用，公式结尾不带编号。

1
2
3
4
5
6

$$
\begin{aligned}
  A_0 & = A + B \\
  & = 3C
\end{aligned}
$$

大括号

\left \right 指令可以生成与后续内容大小匹配的括号。

1
2
3
4
5
6
7
8
9

$$
U(x) = 
\left\{
    \begin{aligned}
    &\infty \ , \ (x>a, x<-a)\\
    &0 \ , \ (-a\leq x\leq a)\\
    \end{aligned}
\right.
$$

矩阵

1
2
3
4
5
6
7
8

$$
\left(
    \begin{matrix}
    1 & 0 \\
    0 & 1 \\
    \end{matrix}
\right)
$$

杂七杂八

使用英文标签

指 figure、Contents 啥的是英文显示。

1

\usepackage[english]{babel}

第5章 模拟调制系统

• 幅度调制（线性调制）原理
  • AM（调幅）
  • DSB（双边带调制）
  • SSB（单边带调制）
    • 滤波法
    • 相移法
  • VSB（残边带调制）
  • 线性调制的一般模型
    • 滤波法
    • 相移法
  • 相干解调
  • 包络检波
• 角度调制（非线性调制）原理
  • FM（调频）& PM（调相）
    • FM & PM 基本概念
    • 单音调制 FM & PM
  • 窄带调频 (NBFM)
  • 宽带调频 (WBFM)
  • 调频信号的产生
    • 直接调频法
    • 间接调频法
    • 正交调制法
  • 调频信号的解调
    • 非相干解调
    • 相干解调
    • 正交解调

幅度调制（线性调制）原理

设正弦型载波为
$$c(t) = A \cos (\omega_c t + \varphi_0)$$
其中

• $A$：载波幅度
• $\omega_c$：载波角频率
• $\varphi_0$：载波初始相位，可假定为 0

则幅度已调信号一般可表示成
$$s_m(t) = A m(t) \cos \omega_c t$$
其中，$m(t)$ 为基带调制信号。

已调信号的频谱
$$S_m(\omega) = \dfrac{A}{2} [M(\omega + \omega_c) + M(\omega - \omega_c)]$$
其中，$M(\omega)$ 为 $m(t)$ 的频谱。

AM（调幅）

标准调幅，常规双边带调制。
将原信号叠加一个直流偏量后于载波相乘，得到带有载波分量的双边带信号。

时域表达式： $$s_{AM}(t) = [A_0 + m(t)] \cos \omega_c t= A_0 \cos \omega_c t + m(t) \cos \omega_c t$$

若 $m(t)$ 为确知信号，则 AM 信号的频谱为：
$$S_{AM}(\omega) = \pi A_0 [\delta(\omega + \omega_c) + \delta(\omega - \omega_c)] + \dfrac{1}{2} [M(\omega + \omega_c) + M(\omega - \omega_c)]$$

当满足条件 $| m(t) |_{max} \leq A_0$ 时，AM 波的包络与调制信号 $m(t)$ 的形状完全一样。

记基带信号的带宽为 $f_H$，则 AM 信号的带宽 $B_{AM} = 2 f_H$。

DSB（双边带调制）

抑制载波双边带信号 (DSB-SC)，简称双边带信号 (DSB)。

时域表达式：
$$s_{DSB}(t) = m(t) \cos \omega_c t$$

频谱：
$$S_{DSB}(\omega) = \dfrac{1}{2} [M(\omega + \omega_c) + M(\omega - \omega_c)]$$

带宽与 AM 信号带宽相同。

SSB（单边带调制）

将双边带信号中的一个边带滤掉。

滤波法

保留上边带，使用高通滤波器；保留下边带，使用低通滤波器。

频谱表示：
$$S_{SSB}(\omega) = S_{DSB}(\omega) \cdot H(\omega)$$

相移法

希尔伯特变换：将原信号相移 $\dfrac{\pi}{2}$，记为 $\hat{}$
希尔伯特滤波器：$H_h(\omega) = -j sgn(\omega)$

时域表达式：
$$s_{SSB}(t) = \dfrac{1}{2} m(t) \cos \omega_c t \mp \dfrac{1}{2} \hat{m}(t) \sin \omega_c t$$
其中，$\hat{m}(t)$ 是 $m(t)$ 的希尔伯特变换。
"$-$" 表示上边带信号，"$+$" 表示下边带信号。

带宽：$B_{SSB} = f_H$

VSB（残边带调制）

跟单边带滤波法类似，只是不像 SSB 中一样完全抑制 DSB 信号的一个边带，而是逐渐切割，使其残留一小部分。

频谱为：
$$S_{VSB}(\omega) = S_{DSB}(\omega) \cdot H(\omega)$$

为保证相干解调的输出无失真地恢复调制信号 $m(t)$，必须要求：
$$H(\omega + \omega_c) + H(\omega - \omega_c) = 常数,\quad |\omega| \leq \omega_H$$
其中，$\omega_H$ 是 $m(t)$ 的截止角频率。

线性调制的一般模型

滤波法

输出已调信号的时域表达式：
$$s_m(t) = [m(t) \cos \omega_c t] * h(t)$$
频域表达式：
$$S_m(\omega) = \dfrac{1}{2} [M(\omega + \omega_c) + M(\omega - \omega_c)] H(\omega)$$

相移法

将 $s_m(t)$ 分解成两个互为正交调制分量，即
$$s_m(t) = s_I(t) \cos \omega_c t + s_Q(t) \sin \omega_c t$$
其中
$$\begin{aligned} &s_I(t) = h_I(t) * m(t),\quad h_I(t) = h(t) \cos \omega_c t \\ &s_Q(t) = h_Q(t) * m(t),\quad h_Q(t) = h(t) \sin \omega_c t \end{aligned}$$

相干解调

适用于所有线性调制信号的解调。
对于 AM 信号，解调后加隔直电容。

接收端提供一个与接收的已调载波严格同步（同频同相）的本地载波（称为相干载波），它与接收的已调信号相乘后，经低通滤波器取出低频分量，即可得到原始的基带调制信号。

送入解调器的已调信号：
$$s_m(t) = s_I(t) \cos \omega_c t + s_Q(t) \sin \omega_c t$$
与相干载波相乘得：
$$s_p(t) = s_m(t) \cos \omega_c t = \dfrac{1}{2} s_I(t) + \dfrac{1}{2} s_I(t) \cos 2\omega_c t + \dfrac{1}{2} s_Q(t) \sin 2\omega_c t$$
经过低通滤波器 (LPF) 后得解调信号：
$$s_d (t) = \dfrac{1}{2} s_I(t) \propto m(t)$$

包络检波

适用于满足 $| m(t) |_{max} \leq A_0$ 条件的 AM 信号。

通常由半波或全波整流器和低通滤波器组成。
在包络的上升阶段，新作用在二极管正极的脉冲比原来脉冲的峰值大。在电容放了一点点电后，新的脉冲到来，使得二极管导通，再次给电容充电。电容电压变化整体趋势是沿着包络上升。
在包络的下降阶段，新作用在二极管正极的脉冲比原来脉冲的峰值小。相对包络上升阶段，电容的充电时刻集中在脉冲的顶部，充电时间相对减小，放电时间相对增多。电容电压变化的整体趋势是沿着包络下降。

检波器的 RC 需要满足条件：
$$f_H \leq \dfrac{1}{RC} \leq f_c$$
其中，$f_H$ 是调制信号的最高频率，$f_c$ 是载波的频率。

条件满足时，检波器的输出为：
$$s_d(t) = A_0 + m(t)$$

角度调制（非线性调制）原理

FM（调频）& PM（调相）

FM & PM 基本概念

角度调制信号的一般表达式为
$$s_m(t) = A \cos [\omega_c t + \varphi(t)]$$
其中

• $A$：载波的恒定振幅
• $\theta(t) = \omega_c t + \varphi(t)$：信号的瞬时相位
• $\omega_c t$：载波相位
• $\varphi(t)$：相对于载波相位的瞬时相位偏移
• $\omega(t) = \dfrac{d[\omega_c t + \varphi(t)]}{dt}$：信号的瞬时角频率
• $\dfrac{d\varphi(t)}{dt}$：相对于载频 $\omega_c$ 的瞬时频率偏移

相位调制 (PM)，指瞬时相位偏移随调制信号 $m(t)$ 作线性变化，即
$$\varphi(t) = K_p m(t)$$
其中，$K_p$ 为调相灵敏度 $(rad/V)$，含义是单位调制幅度引起 PM 信号的相位偏移量。
带入可得调相信号为
$$s_{PM}(t) = A\cos [\omega_c t + K_p m(t)]$$

频率调制 (FM)，指瞬时频率偏移随调制信号 $m(t)$ 成比例变化，即
$$\dfrac{d\varphi(t)}{dt} = K_f m(t)$$
其中，$K_f$ 为调频灵敏度 $(rad/(s \cdot V))$。
这时，相位偏移为
$$\varphi(t) = K_f \int m(\tau) d\tau$$
带入可得调频信号为
$$s_{FM} (t) = A \cos [\omega_c t + K_f \int m(\tau) d\tau]$$

单音调制 FM & PM

设调制信号为单一频率的正弦波，即
$$m(t) = A_m \cos \omega_m t = A_m \cos 2\pi f_m t$$

PM 信号：
$$s_{PM}(t) = A \cos[\omega_c t + m_p \cos \omega_m t]$$
其中，$m_p = K_p A_m$ 称为调相指数，表示最大的相位偏移。

FM 信号：
$$s_{FM}(t) = A \cos[\omega_c t + m_f \sin \omega_m t]$$
其中

• $m_f = \dfrac{K_f A_m}{\omega_m} = \dfrac{\Delta \omega}{\omega_m} = \dfrac{\Delta f}{f_m}$：调频指数，表示最大的相位偏移
• $\Delta \omega = K_f A_m$：最大角频偏
• $\Delta f = m_f \cdot f_m$：最大频偏

窄带调频 (NBFM)

FM 信号的最大瞬时相位偏移满足
$$\left| K_f \int m(\tau) d\tau \right| \ll \dfrac{\pi}{6}\ (或 0.5)$$
此时有
$$\begin{aligned} &\cos \left[ K_f \int m(\tau) d\tau \right] \approx 1 \\ &\sin\left[ K_f \int m(\tau) d\tau \right] \approx K_f \int m(\tau) d\tau \end{aligned}$$

FM 信号的时域表达式可化简为
$$s_{NBFM}(t) \approx A \cos \omega_c t - \left[ A K_f \int m(\tau) d\tau \right] \sin \omega_c t$$
对应的频域表达式为
$$S_{NBFM}(\omega) = \pi A [\delta(\omega + \omega_c) + \delta(\omega - \omega_c)] + \dfrac{A K_f}{2} \left[\dfrac{M(\omega - \omega_c)}{\omega - \omega_c} - \dfrac{M(\omega + \omega_c)}{\omega + \omega_c}\right]$$
带宽与 AM 信号相同，都为调制信号最高频率的两倍。

宽带调频 (WBFM)

最大瞬时相位偏移不满足窄带调频的条件。

设单音调制信号为
$$m(t) = A_m \cos \omega_m t = A_m \cos 2\pi f_m t$$
利用傅里叶极数展开可得
$$\begin{aligned} &\cos (m_f \sin \omega_m t) = J_0(m_f) + \sum\limits_{n=1}^{\infty} 2J_{2n}(m_f) \cos 2n \omega_m t \\ &\sin (m_f \sin \omega_m t) = 2\sum\limits_{n=1}^{\infty} J_{2n-1}(m_f) \sin (2n-1) \omega_m t \end{aligned}$$
其中，$J_n(m_f)$ 为第一类 n 阶贝塞尔函数，具有以下性质
$$\begin{aligned} &J_{-n}(m_f) = -J_n(m_f)\quad n 为奇数 \\ &J_{-n}(m_f) = J_n(m_f)\quad n 为偶数 \end{aligned}$$

可以得到 FM 信号的级数展开形式为
$$s_{FM}(t) = A\sum\limits_{-\infty}^{\infty} J_n(m_f) \cos (\omega_c + n\omega_m)t$$
对应的频域表达式为
$$S_{FM}(\omega) = \pi A\sum\limits_{-\infty}^{\infty} J_n(m_f) [\delta(\omega - \omega_c - n\omega_m) + \delta(\omega + \omega_c + n\omega_m)]$$
带宽为
$$B_{FM} = 2(m_f + 1)f_m = 2(\Delta f + f_m)$$
当 $m_f \ll 1$ 时，$B_{FM} \approx 2f_m$ (NBFM)；
当 $m_f \gg 1$ 时，$B_{FM} \approx 2\Delta f$ (WBFM)。

调频信号的产生

直接调频法

用调制信号直接控制载波振荡器的频率，使其按调制信号的规律线性地变化。

锁相环 (PLL) 调制器：使输出振荡器信号与参考信号同步。

• 晶体振荡器：产生频率稳定、精确的信号。

• 相位检测器 (PD)：对两个信号的相位进行比较，并根据两个信号的相位差产生一个电压。
  通常由模拟乘法器组成，两个输入信号分别为晶振的输出和 VCO 输出的 FM 信号。

  设晶振的输出信号和 VCO 的输出信号分别为
  $$\begin{aligned} &u_i(t) = U_{im} \sin [\omega_i t + \theta_i (t)] \\ &u_o(t) = U_{om} \sin [\omega_o t + \theta_o (t)] \end{aligned}$$
  则模拟乘法器的输出电压为
  $$\begin{aligned} u_D(t) &= K u_i(t) u_o(t) \\ &= \dfrac{1}{2} K U_{im} U_{om} \sin[(\omega_i t + \theta_i(t)) + (\omega_o t + \theta_o(t))] \\ &+ \dfrac{1}{2} K U_{im} U_{om} \sin[(\omega_i t + \theta_i(t)) - (\omega_o t + \theta_o(t))] \end{aligned}$$

• 环路滤波器 (LF)：为低通滤波器。过滤 PD 的输出，即过滤掉 $u_D(t)$ 中的和频分量，留下差频分量作为 VCO 的输入信号的一部分。

  PD 的输出信号为
  $$\begin{aligned} u_C(t) &= \dfrac{1}{2} K U_{im} U_{om} \sin[(\omega_i t + \theta_i(t)) - (\omega_o t + \theta_o(t))] \\ &= U_{dm} \sin[(\omega_i - \omega_o)t + (\theta_i(t) - \theta_o(t))] \end{aligned}$$
  当锁相环进入相位锁定状态时，$u_C(t)$ 为恒定值，不随时间变化。

• 压控振荡器 (VCO)：由外部电压控制振荡频率的振荡器，振荡频率正比于输入控制电压。
  用于产生调频信号，通常被认为是回路的输出。

  将 LF 的输出和调制信号 $m(t)$ 叠加后输入 VCO，可得输出信号的瞬时角频率为
  $$\omega(t) = \omega_0 + K_f m(t)$$

间接调频法

先将调制信号积分，然后对载波进行调相，即可产生一个 NBFM 信号，再经过 n 次倍频器得到 WBFM 信号。

记调制信号为 $m(t)$，载波为 $A \cos \omega_c t$。

• 产生 NBFM 信号

  • 将 $m(t)$ 输入积分器，得到
    $$K_f \int m(\tau) d\tau$$
  • 对载波进行调相，使其相位 $-\dfrac{\pi}{2}$，得到
    $$A \sin \omega_c t$$
  • 将两个信号相乘后，用原载波信号减去相乘结果，得到 NBFM 信号为
    $$s_{NBFM} = A \cos \omega_c t - \left[A K_f \int m(\tau) d\tau\right]\sin \omega_c t$$

• 通过倍频器，提高调频指数 $m_f$，得到 WBFM 信号。

  • 倍频器可用非线性器件实现，然后通过带通滤波器滤去不需要的频率分量。
    以理想平方律器件为例，其输入输出特性为 $s_o(t) = a s_i^2(t)$。

    当输入信号为调频信号时有
    $$\begin{aligned} s_i(t) &= A \cos [\omega_c t + \varphi(t)] \\ s_o(t) &= \dfrac{1}{2} aA^2 [1 + \cos(2\omega_c t + 2 \varphi(t))] \end{aligned}$$
    滤除直流成分后得到一个新的调频信号，其载频和相位偏移均增加到原来的 2 倍，因此 $m_f$ 也增为原来的 2 倍。
    同理，经过 n 次倍频后增加为原来的 n 倍。

  • 倍频器在提高相位偏移的同时也会提高载波频率，需要混频器进行下变频来使载波频率符合要求。

    记原载频为 $f_1$，经过 $n_1$ 次倍频得到的频率为 $n_1 f_1$；
    记混频器参考频率为 $f_2$，则调频发射信号的载频为 $f_c = n_2(n_1 f_1 - f_2)$。

正交调制法

• 对调制信号 $m(t)$ 进行积分，得到
  $$\Phi = K_f \int m(\tau) d\tau$$

• 对积分后的信号分别取余弦和正弦，得到 I 路数据和 Q 路数据为
  $$\begin{aligned} I(t) &= \cos(\Phi) \\ Q(t) &= \sin(\Phi) \end{aligned}$$

• 两路信号分别乘上载波 $A\cos (\omega_c t)$ 和 $-A\sin (\omega_c t)$ 相加，得到 FM 信号为
  $$\begin{aligned} s_{FM}(t) &= A I(t) \cos (\omega_c t) - A Q(t) \sin (\omega_c t) \\ &= A \cos (\omega_c t + \Phi) \end{aligned}$$

  也可以将 $I(t)$ 和 $Q(t)$ 组成一个复信号 $Z(t) = I(t) + j Q(t)$，然后乘以复载波 $\exp (j\omega_c t)$，取实部得 FM 信号
  $$s_{FM}(t) = Re \{Z(t) \exp (j\omega_c t)\}$$

调频信号的解调

调频信号的解调要产生一个与输入调频信号的频率呈线性关系的输出电压。
使用鉴频器来完成这种频率-电压转换关系。

非相干解调

NBFM 信号和 WBFM 信号都适用。

调频信号的一般表达式为
$$s_{FM} (t) = A \cos [\omega_c t + K_f \int m(\tau) d\tau]$$

常见的鉴频器为微分器和包络检波器。

• 将调频信号通过一个带通滤波器 (BPF) 和限幅器。
  BPF 滤除带外噪声及高次谐波分量。
  限幅器消除信道中噪声和其他原因引起的调频波的幅度起伏。

• 对限幅器输出的信号求微分，即把幅度恒定的调频信号变成幅度和频率都随调制信号 $m(t)$ 变化的调幅调频波 $s_d(t)$。
  $$\begin{aligned} s_d(t) &= \dfrac{d s_{FM}(t)}{dt} \\ &= -A[\omega_c + K_f m(t)] \sin \left[\omega_c t + K_f \int m(\tau) d\tau\right] \end{aligned}$$

• 通过包络检波器将其幅度变化检出并滤去直流，与 AM 信号的包络检波同理。

• 通过一个低通滤波器，滤除高频载波 ($2\omega_c$ 或 $\omega_c$)，得到解调输出
  $$m_o(t) = K_d K_f m(t)$$
  其中 $K_d$ 为鉴频灵敏度 $(V/(rad/s))$

相干解调

仅适用于 NBFM 信号。

窄带调频信号的表达式为
$$s_{NBFM}(t) = A \cos \omega_c t - A \left[ K_f \int m(\tau) d\tau \right] \sin \omega_c t$$
相干载波为
$$c(t) = -\sin \omega_c t$$

• 将 NBFM 信号与相干载波相乘，得到
  $$s_p(t) = -\dfrac{A}{2} \sin 2\omega_c t + \dfrac{A}{2} \left[ K_f \int m(\tau) d\tau \right] (1 - \cos 2\omega_c t)$$

• 经过低通滤波器取出其低频分量
  $$s_d(t) = \dfrac{A}{2} \left[ K_f \int m(\tau) d\tau \right]$$

• 经过微分器，得到解调输出
  $$m_o(t) = \dfrac{A K_f}{2} m(t)$$

正交解调

正交解调也属于相干解调的一种，但具有较强的抗载频失配能力，不要求相干载波严格的同频同相。

记 $\Phi = K_f \int m(\tau) d\tau$
原调频信号为
$$\begin{aligned} s_{FM} (t) &= A \cos [\omega_c t + K_f \int m(\tau) d\tau] \\ &= A \cos (\omega_c t + \Phi) \end{aligned}$$

• 乘以正交相干载波得到 $s_I(t)$ 和 $s_Q(t)$，即
  $$\begin{aligned} s_I(t) &= s_{FM}(t) \cos (\omega_c t) \\ &= \frac{A}{2} \cos(2\omega_c t + \Phi) + \dfrac{A}{2} \cos(\Phi) \\ s_Q(t) &= -s_{FM}(t) \sin (\omega_c t) \\ &= -\frac{A}{2} \sin(2\omega_c t + \Phi) + \dfrac{A}{2} \sin(\Phi) \end{aligned}$$

• 通过低通滤波器，滤除高频分量可得
  $$\begin{aligned} s_I(t) &= \dfrac{A}{2} \cos(\Phi) \\ s_Q(t) &= \dfrac{A}{2} \sin(\Phi) \end{aligned}$$

• 通过反正切计算相位
  $$K_f \int m(\tau) d\tau = \Phi(t) = atan\left[\dfrac{s_Q(t)}{s_I(t)}\right]$$

• 通过一个微分器得到解调结果 $m_o(t)$

• 对于数字信号，可以采用改良算法，将上述两步合并成一步，得到
  $$m_o(n) = \dfrac{s_I(n-1) s_Q(n) - s_I(n) s_Q(n-1)}{s^2_I(n) + s^2_Q(n)}$$

• 杂七杂八
  • 卷积
    • 线性卷积
    • 圆周卷积
  • 模拟信号采样
  • 数学不好
• 信号变换
  • 傅里叶变换
    • 连续时间
      • CFS
      • CFT
    • 离散时间
      • DTFS
      • DTFT
    • 特点
  • z 变换
    • 双边
      • 定义
      • 常见 z 变换对
      • 性质
      • 逆变换
    • 单边
    • 与傅里叶变换的关系
• DFT & FFT
  • DFT & IDFT 的计算
  • 基2 FFT 算法
    • 按时间抽取
      • 蝶形运算
    • 按频率抽取
  • 基4 FFT 算法
  • N 为复合数的 FFT 算法
  • 调频 z 变换算法
• 离散时间系统
  • 系统函数
  • FIR 系统
    • 直接型结构
    • 级联型结构
  • IIR 系统
    • 直接型结构
      • 直接 I 型
      • 直接 II 型
    • 级联型结构
    • 并联型结构
• 滤波器设计
  • 数字滤波器
    • 技术指标
    • 频率响应
  • IIR 滤波器
    • 模拟滤波器
      • 巴特沃斯低通滤波器
      • 切比雪夫 I 型低通滤波器
      • 模拟频域频带变换
    • 间接法设计数字滤波器
      • 冲激响应不变法
      • 双线性变换法
      • 数字频域频带变换
  • FIR 滤波器
    • 滤波器特点
    • 窗函数设计法
      • 计算步骤
    • 频率抽样设计法
      • 基本思路
      • 设计公式
    • 与 IIR 比较

杂七杂八

卷积

线性卷积

$$x(n) * h(n) = \sum\limits_{k = -\infty}^{\infty} x(k)h(n-k)$$

• 恒等性：$x(n)*\delta(n) = x(n)$
• 位移性：$x(n)*\delta(n-k) = x(n-k)$
• 交换律：$x(n)*h(n) = h(n)*x(n)$
• 结合律：$[x_1(n)*h_1(n)]*h_2(n) = x_1(n)*[h_1(n)*h_2(n)]$
• 分配律：$x(n)*[h_1(n) + h_2(n)] = x_1(n)*h_1(n) + x_1(n)*h_2(n)$

圆周卷积

对于两个长度为 N 的序列 $x(n)$ 和 $h(n)$：
$$x(n) \otimes h(n) = \sum\limits_{k=0}^{N-1} x(k) [h(n-k) \mod N]$$
即将 $h(n)$ 扩充为周期为 N 的序列。

可以通过 DFT 和 IDFT 的计算获得圆周卷积的结果： - 对输入序列 x(n) 和 h(n) 分别进行 0 填充，使二者长度均变为 2N-1。 - 对填充后的序列做 2N-1 点 DFT，得到 X(k) 和 H(k)。 - 对 X(k)H(k) 这个乘积做 IDFT，即可得到圆周卷积的结果。

模拟信号采样

$$x(n) = x_a(nT)$$

• 模拟信号频率：$-\infty < F < \infty,\ -\infty < \Omega < \infty$

• 采样周期：$T$

• 采样频率：$F_s = \dfrac{1}{T}$

• 离散信号频率：$-\dfrac{1}{2} < f = \dfrac{F}{F_s} < \dfrac{1}{2},\ -\pi < \omega = \Omega T < \pi$

• 对某一采样率 $F_s$：$F_{max} = \dfrac{F_s}{2} = \dfrac{1}{2T},\ \Omega_{max} = \pi F_s = \dfrac{\pi}{T}$
  超过的部分会发生混叠。

数学不好

• $\sin \theta = \dfrac{1}{2}(e^{j\theta} - e^{-j\theta}),\ \cos \theta = \dfrac{1}{2}(e^{j\theta} + e^{-j\theta})$

信号变换

傅里叶变换

连续时间

连续时间信号具有非周期频谱。

CFS

连续时间周期信号的傅里叶极数。

其中，$T_p = \dfrac{1}{F_0}$ 为信号 $x(t)$ 的基本周期。

一个周期信号具有无限能量，但具有一个有限的平均功率。
功率信号的帕塞瓦关系式：
$$P_x = \dfrac{1}{T_p} \displaystyle \int_{T_p} |x(t)|^2 dt = \sum\limits_{k = -\infty}^{\infty} |c_k|^2$$

功率密度谱：以频率 $F = kF_0$ 为横轴，$|c_k|^2$ 为纵轴，偶对称。

$c_k$ 幅度谱偶对称，相位谱奇对称。

CFT

连续时间非周期信号的傅里叶变换。

如果是有限时长的信号，修改积分上下限即可。

非周期有限能量信号的帕塞瓦关系式：
$$E_x = \displaystyle \int_{-\infty}^{\infty} |x(t)|^2 dt = \displaystyle \int_{-\infty}^{\infty} |X(F)|^2 dF$$

能量密度谱：以频率 $F$ 为横轴，$S_{xx} = |X(F)|^2$ 为纵轴。
实信号的能量密度谱偶对称，频域幅度谱偶对称，相位谱奇对称。

离散时间

DTFS

离散时间周期信号的傅里叶极数。

其中 $k = 0, 1, \cdots, N-1$。
如果扩展到该范围之外，则 $c_{k+N} = c_k$，即 $c_k$ 是周期为 $N$ 的序列。

离散周期信号的帕塞瓦关系式：
$$P_x = \sum\limits_{k=0}^{N-1} |c_k|^2 = \dfrac{1}{N} \sum\limits_{n=0}^{N-1} |x(n)|^2$$

与连续时间周期信号一样，频域幅度谱偶对称，相位谱奇对称。

DTFT

离散时间非周期信号的傅里叶变换。

记 $X_N(\omega) = \sum\limits_{n = -N}^{N} x(n) e^{-j \omega n}$
Gibbs 现象：在 $X(\omega)$ 的一个不连续点处，$X_N(\omega)$ 逼近 $X(\omega)$ 的振荡行为。

有限能量的离散时间非周期信号的帕塞瓦关系式：
$$E_x = \sum\limits_{n = -\infty}^{\infty} |x(n)|^2 = \dfrac{1}{2\pi} \displaystyle\int_{-\pi}^{\pi} |X(\Omega)|^2$$

记 $S_{xx} = |X(\omega)|^2$，能量密度谱。
对于实信号，频域幅度谱偶对称，相位谱奇对称，能量密度谱偶对称。

特点

• 连续时间信号具有非周期频谱。
• 离散时间信号具有周期频谱。
• 周期信号具有离散频谱。
• 非周期有限能量信号具有连续频谱。

z 变换

双边

定义

$$X(z) = \sum\limits_{n = -\infty}^{\infty} x(n) z^{-n}$$

收敛域： - 因果序列：$|z| > r_2$ - 非因果序列：$|z| < r_1$ - 双边序列：$r_1 < |z| < r_2$

常见 z 变换对

性质

逆变换

• 围线积分法 $$x(n) = \sum\limits_{z_i}\left[X(z)z^{n-1} 在 z=z_i 的留数\right]$$

  对于 m 阶极点 a，f(z) 的留数为： $$\dfrac{1}{(m-1)!} \lim\limits_{z \rightarrow a}\left[(z - a)^m f(z)\right]^{(m-1)}$$

• 幂级数展开法
  $$X(z) = \sum\limits_{n=-\infty}^{\infty} c_n z^{-n} \rightarrow x(n) = c_n$$

  采用长除法

  • 因果序列：高次幂在前
  • 非因果序列：低次幂在前

• 部分分式展开法

  • $X(z)$ 有两个相异极点 $p_1,\ p_2$
    $$X(z) = \dfrac{A_1}{z-p_1} + \dfrac{A_2}{z-p_2}$$

  • $X(z)$ 有两个相同极点 $p$
    $$X(z) = \dfrac{A_1}{z-p} + \dfrac{A_2}{(z-p)^2}$$

单边

$$X^+(z) = \sum\limits_{n=0}^{\infty} x(n)z^{-n}$$

与傅里叶变换的关系

$$X(z=e^{j\omega}) = X(\omega) = \sum\limits_{n = -\infty}^{\infty} x(n) e^{-j\omega n}$$

DFT & FFT

DFT & IDFT 的计算

记 $$W_N = e^{-j 2\pi / N}$$ $W_N$ 具有对称性和周期性，即 $$W_N^{k + N/2} = -W_N^k$$ $$W_N^{k + N} = W_N^k$$

DFT：对长为 N 的数据序列 x(n) 计算长度为 N 的复序列 X(k)。
IDFT：DFT 的逆变换。

对每个 k 值，直接计算 X(k) 涉及 N 次复数乘法（4N 次实数乘法）和 N-1 次复数加法（4N-2 次实数加法）。
因此计算长度为 N 的 DFT 要求 $N^2$ 次复数乘法和 $N^2 - N$ 次复数加法。

基2 FFT 算法

适用于 $N = 2^v$。

按时间抽取

将 $x(n)$ 划分为奇序列和偶序列（以 2 为因子抽取），即 $$f_1(n) = x(2n),\quad f_2(n) = x(2n + 1)\quad (n = 0, 1, \cdots, \frac{N}{2}-1)$$

二者的 $\frac{N}{2}$ 点 DFT 结果分别为 $F_1(k)$、$F_2(k)$。

N 点 DFT 算法用抽取序列的 DFT 可表示为： $$\begin{aligned} X(k) &= \sum\limits_{n=0}^{N-1} x(n) W_N^{kn},\quad k = 0,1, \cdots, N-1 \\ &= \sum\limits_{n为偶数} x(n) W_N^{kn} + \sum\limits_{n为奇数} x(n) W_N^{kn} \\ &= \sum\limits_{m=0}^{(N/2)-1} x(2m) W_N^{2mk} + \sum\limits_{m=0}^{(N/2)-1} x(2m+1) W_N^{(2m+1)k} \\ &= \sum\limits_{m=0}^{(N/2)-1} f_1(m) W_{N/2}^{mk} + W_N^k \sum\limits_{m=0}^{(N/2)-1} f_2(m) W_{N/2}^{mk} \\ &= F_1(k) + W_N^k F_2(k),\quad k = 0,1, \cdots, \frac{N}{2}-1 \\ X(k + \frac{N}{2}) &= F_1(k) - W_N^k F_2(k) \end{aligned}$$

直接计算 $F_1(k)$ 需要 $(\frac{N}{2})^2$ 次复数乘法，直接计算 $F_2(k)$ 同理，计算 $W_N^k F_2(k)$ 还需要 $\frac{N}{2}$ 次复数乘法。
所以，计算 $X(k)$ 一共需要 $\frac{N^2 + N}{2}$ 次复数乘法。

同样的，对 $F_1(k)$和$F_2(k)$ 的计算也可以通过计算 $\frac{N}{4}$ 点 DFT 来完成，从而只需要 $\frac{N^2 + 2N}{4}$ 次复数乘法。
这时计算 $X(k)$ 一共需要 $\frac{N^2}{4} + N$ 次复数乘法。

数据序列的抽取可以不断重复，直到最后序列变为 1 点序列。
对于$N = 2^v$，抽取次数为 $v$，复数乘法总次数减少为 $\frac{N}{2} \log_2(N)$，复数加法的次数为 $N \log_2(N)$。

eg. 如果 $x(n)$ 为 N 点实信号
从上述推导中可以得出：
$$\begin{aligned} F_1(k) &= \dfrac{1}{2} \left[ X(k) + X(k + \frac{N}{2})\right] \\ F_2(k) &= \dfrac{1}{2} \left[ X(k) - X(k + \frac{N}{2})\right] W_N^{-k} \end{aligned}$$
其中 $k = 0, 1, \cdots, \frac{N}{2} - 1$。
令 $y(n) = f_1(n) + j f_2(n)$，易得 $Y(k) = F_1(k) + j F_2(k)$。
已知 $y(n)$，则可以通过计算 $Y(k)$（$\frac{N}{2}$ 点 DFT）得到 $X(k)$（$N$ 点 DFT）；
已知 $Y(k)$，则可以通过计算 $y(n)$（$\frac{N}{2}$ 点 IDFT）得到 $x(n)$（$N$ 点 IDFT）。

蝶形运算

对一对复数 (a, b)，将 b 乘上 $W_N^k$ 然后 a 加上或减去这个积，得到一对新的复数 (A, B)。

对于一个 2 点序列 $x(0)$、$x(1)$，它们各自做 1 点 DFT，得到的结果就是它们自身，因此按上述基 2 FFT 算法，它们的 2 点 DFT 结果为 $X(0) = x(0) + W_2^0 x(1)$、$X(1) = x(0) - W_2^0 x(1)$。
即上述蝶形运算中 $a = x(0)$、$b = x(1)$、$A = X(0)$、$B = X(1)$。

eg. 计算 8 点基 2 FFT

• 序列抽取
  • 第一次抽取：
    • $x(0), x(2), x(4), x(6)$
    • $x(1), x(3), x(5), x(7)$
      
  • 第二次抽取：
    • $x(0), x(4)$
    • $x(2), x(6)$
    • $x(1), x(5)$
    • $x(3), x(7)$
      
  • 第三次抽取：
    $y(n)$ 表示当前位置存储的值。
    • $y(0) = x(0)$
      
    • $y(1) = x(4)$
    • $y(2) = x(2)$
    • $y(3) = x(6)$
    • $y(4) = x(1)$
    • $y(5) = x(5)$
    • $y(6) = x(3)$
    • $y(6) = x(7)$
• DFT 计算
  • 第一阶段：4 级 4 组蝶形运算
    • $x(0), x(4)$ 的 2 点 DFT 结果：
      $y(0) = y(0) + W_2^0 y(1) = y(0) + W_8^0 y(1)$
      $y(1) = y(0) - W_2^0 y(1) = y(0) - W_8^0 y(1)$
    • 后续 $y(n)$ 的算法相同
  • 第二阶段：2 级 4 组蝶形运算
    • $x(0), x(2), x(4), x(6)$ 4 点 DFT 结果：
      $y(0) = y(0) + W_4^0 y(2) = y(0) + W_8^0y(2)$
      $y(1) = y(1) + W_4^1 y(3) = y(1) + W_8^2y(3)$
      $y(2) = y(0) - W_4^0 y(2) = y(0) - W_8^0y(2)$
      $y(3) = y(1) - W_4^1 y(3) = y(1) - W_8^2y(3)$
    • $x(1), x(3), x(5), x(7)$ 4 点 DFT 运算方式相同
  • 第三阶段：1 级 4 组蝶形运算
    • $y(0) = y(0) + W_8^0 y(4)$
      $y(1) = y(1) + W_8^1 y(5)$
      $y(2) = y(2) + W_8^2 y(6)$
      $y(3) = y(3) + W_8^3 y(7)$
      $y(4) = y(0) - W_8^0 y(4)$
      $y(5) = y(1) - W_8^1 y(5)$
      $y(6) = y(2) - W_8^2 y(6)$
      $y(7) = y(3) - W_8^3 y(7)$
    • $X(k) = y(k)$

按频率抽取

将 DFT 公式分为前 $\frac{N}{2}$ 个数据点的求和与后 $\frac{N}{2}$ 个数据点的求和： $$\begin{aligned} X(k) &= \sum\limits_{m=0}^{(N/2)-1} x(n) W_N^{kn} + \sum\limits_{m=N/2}^{N-1} x(n) W_N^{kn} \\ & = \sum\limits_{m=0}^{(N/2)-1} x(n) W_N^{kn} + W_N^{kn} \sum\limits_{m=0}^{(N/2)-1} x(n + \frac{N}{2}) W_N^{kn} \\ & = \sum\limits_{m=0}^{(N/2)-1} \left[ x(n) + (-1)^k x(n + \frac{N}{2})\right] W_N^{kn} \end{aligned}$$

将 $X(k)$ 分拆成奇序列和偶序列：
$$\begin{aligned} X(2k) &= \sum\limits_{m=0}^{(N/2)-1} \left[ x(n) + x(n + \frac{N}{2})\right] W_{N/2}^{kn} \\ X(2k+1) &= \sum\limits_{m=0}^{(N/2)-1} \left\{ \left[ x(n) - x(n + \frac{N}{2})\right] W_N^{n} \right\} W_{N/2}^{kn} \end{aligned}$$

定义 $\frac{N}{2}$ 点序列：
$$\begin{aligned} g_1(n) &= x(n) + x(n + \frac{N}{2}) \\ g_2(n) &= \left[ x(n) - x(n + \frac{N}{2})\right] W_N^{n},\quad n = 0,1, \cdots, \frac{N}{2}-1 \end{aligned}$$

则有 $$\begin{aligned} X(2k) &= \sum\limits_{m=0}^{(N/2)-1} g_1(n) W_{N/2}^{kn} \\ X(2k+1) &= \sum\limits_{m=0}^{(N/2)-1} g_2(n) W_{N/2}^{kn} \end{aligned}$$

与按时间抽取类似的，该过程可以重复抽取。
整个计算过程的抽取次数、复数乘法次数、复数加法次数均与按时间抽取相同。

基4 FFT 算法

$N = 4^v$

与基2 FFT 算法的推导方式类似，将隔 2 个进行一次抽取改为隔 4 个进行一次抽取。
令 $$\begin{aligned} x_0(n) &= x(4n) \\ x_1(n) &= x(4n+1) \\ x_2(n) &= x(4n+2) \\ x_3(n) &= x(4n+3),\quad 0 \leq n \leq \frac{N}{4} - 1 \end{aligned}$$

可以得到 $$\left[ \begin{matrix} X(k) \\ X(k + \frac{N}{4}) \\ X(k + \frac{N}{2}) \\ X(k + \frac{3N}{4}) \end{matrix} \right] = \left[ \begin{matrix} 1 & 1 & 1 & 1 \\ 1 & -j & -1 & j \\ 1 & -1 & 1 & -1 \\ 1 & j & -1 & -j \end{matrix} \right] \cdot \left[ \begin{matrix} X_0(k) \\ W_N^k X_1(k) \\ W_N^2k X_2(k) \\ W_N^3k X_3(k) \end{matrix} \right]$$

按此方法继续抽取即可。

N 为复合数的 FFT 算法

将 N 分解为两个整数的乘积：$N = LM$。如果 N 是质数可以通过加 0 的方式使其满足该分解。
令 $0 \leq l \leq L-1$，$0 \leq m \leq M-1$；则可以选择映射 $n = Ml + m$，即 $x(n) = x(l, m)$，相当于将原序列分为 L 组，每组的长度为 M。
同时 $X(k)$ 被映射为 $X(p, q)$，即 $k = Mp + q\ (0 \leq p \leq L-1,\ 0 \leq q \leq M-1)$。

• 对每一组计算 M 点 DFT： $$F(l, q) = \sum\limits_{m=0}^{M-1} x(l, m) W_M^{mq}$$

• 计算 L 点 DFT：
  $$X(p, q) = \sum\limits_{l=0}^{L-1} W_N^{lq} F(l, q) W_L^{lp}$$

需要复数乘法 $N(M+L+1)$ 次，复数加法 $N(M+L-2)$ 次。

同理可以选择映射 $n = Lm + l$，即将原序列分为 M 组，每组长度为 L。
计算方法类似。

调频 z 变换算法

N 点数据序列 x(n) 的 DFT 可视为单位圆上均匀分布的 N 点 z 变换。

计算 $x(n)$ 在点集 $\{z_k\}$ 上的 z 变换
其中等高线是一个以 r 为半径的圆，且 $z_k$ 是 N 个等间距点，即 $z_k = r W_N^{k}$
则有：
$$\begin{aligned} X(z_k) &= \sum\limits_{n=0}^{N-1} x(n) z_k^{-n} \\ &= \sum\limits_{n=0}^{N-1} [x(n) r^{-n}] W_N^{-kn} \end{aligned}$$
即计算 $x(n) r^{-n}$ 的 DFT。

离散时间系统

系统函数

用 N 阶差分方程描述：
$$y(n) = -\sum\limits_{k=1}^{N} a_k y(n-k) + \sum\limits_{k=0}^{M} b_k x(n-k)$$

对应的系统函数：
$$H(z) = \dfrac{Y(z)}{X(z)}= \dfrac{\sum\limits_{k=0}^{M} b_k z^{-k}}{1 + \sum\limits_{k=1}^{N} a_k z^{-k}}$$

• $a_k \neq 0,\ b_k \neq 0$（既有零点又有极点）：零极点系统，IIR 系统
• $a_k = 0$（只有零点）：全零点系统，FIR 系统
• $b_k = 0$（包含 N 个极点和一个 z=0 的 N 阶零点）：全极点系统，IIR 系统

FIR 系统

具有有限长冲激响应的系统。
系统函数里不包含极点。

差分方程描述：
$$y(n) = \sum\limits_{k=0}^{M-1} b_k x(n-k)$$

系统函数描述：
$$H(z) = \sum\limits_{k=0}^{M-1} b_k z^{-k}$$

单位冲激响应：
$$h(n) = \left\{ \begin{aligned} &b_n,\quad 0 \leq n \leq M-1 \\ &0,\quad else \end{aligned} \right.$$

直接型结构

(P. 419)
对 $b_k x(n-k)$，将 $x(n)$ 经过 k 个延时器（即 $z^{-1}$）后乘 $b_k$（即 $h(k)$），在将每个 k 值对应的结果通过加法器相加得到结果。

该结构需要 M-1 个存储空间来存放 M-1 个输入，每个输出需要 M 次乘法和 M-1 次加法。

当 FIR 系统具有线性相位时，单位冲激响应函数服从下面对称或不对称条件：
$$h(n) = \pm h(M-1-n)$$

对称的部分可以在延时后先相加，再一起乘对应的 $h(k)$，因此乘法减为 $\frac{M}{2}$（M 为偶数）次或 $\frac{M - 1}{2}$（M 为奇数）次。

级联型结构

将 $H(z)$ 拆分成多个 $H_k(z)$ 相乘。
用直接型结构实现 $H_k(z)$ 再将它们级联起来。

IIR 系统

具有无限长冲激响应的系统。
系统函数里包含极点。

直接型结构

差分方程描述和系统函数描述与系统函数中的相同。

可以视为级联的两个系统，即 $H(z) = H_1(z) H_2(z)$
其中 $H_1(z)$ 包含 $H(z)$ 的零点，$H_2(z)$ 包含 $H(z)$ 的极点，即 $$H_1(z) = \sum\limits_{k=0}^{M} b_k z^{-k}$$ $$H_2(z) = \dfrac{1}{1 + \sum\limits_{k=1}^{N} a_k z^{-k}}$$

这里面 $H_1(z)$ 是一个 FIR 系统，$H_2(z)$ 是全极点系统。

直接 I 型

将 $H_1(z)$ 和 $H_2(z)$ 分别使用直接型结构实现再级联起来即可。

需要 M+N+1 次乘法，M+N 次加法和 M+N+1 个存储空间。

直接 II 型

交换直接 I 型中 $H_1(z)$ 和 $H_2(z)$ 对应结构的位置，即将 $H_2(z)$ 置于 $H_1(z)$ 之前，二者公用一组延迟器。

需要 M+N+1 次乘法，M+N 次加法和 max{M, N} 个存储空间。

级联型结构

与 FIR 的级联型结构类似，同样是将 $H(z)$ 拆分成多个 $H_k(z)$ 相乘，每个 $H_k(z)$ 用直接型结构实现再级联起来。

并联型结构

假设 $N \geq M$ 且极点是独立的，对 $H(z)$ 使用部分分式展开法： $$H(z) = C + \sum\limits_{k=1}^{N} \dfrac{A_k}{1 - p_k z^{-1}} = C + \sum\limits_{k=1}^{K} H_k(z)$$ 其中，$p_k$ 是极点，$A_k$ 是部分分式展开的系数，$C = \frac{b_N}{a_N}$。

分别用直接型结构实现 $H_k(z)$ 再并联起来即可。

滤波器设计

数字滤波器

技术指标

技术指标以其频率响应的幅度特性给出，有通带、阻带和过渡带。

• 通带
  • 通带截止频率：$\omega_p$
  • 通带波纹：$\delta_1$
  • 通带允许最大衰减：$R_p \geq -20\lg (1-\delta_1)\ (dB)$
• 阻带
  • 阻带截止频率：$w_{st}$
  • 阻带波纹：$\delta_2$
  • 阻带应达到的最小衰减：$A_s \leq -20\lg (\delta_2)\ (dB)$

频率响应

• 幅度平方响应：
  $$| H(e^{j\omega}) |^2 = H(z)H(z^{-1}) |_{z=e^{j\omega}}$$

• 相位响应：
  $$\beta (e^{j\omega}) = \dfrac{1}{2j} \ln \left[ \dfrac{H(z)}{H(z^{-1})}\right]_{z = e^{j\omega}}$$

• 群延迟响应：
  $$\tau (e^{j\omega}) = -\dfrac{d \beta (e^{j\omega})}{d \omega}$$
  是滤波器平均延时的一个度量。
  当滤波器满足线性相位响应特性时，通带内群延迟为常数。

IIR 滤波器

模拟滤波器

巴特沃斯低通滤波器

已知的参数 - 通带截止频率：$\Omega_p$ - 阻带截止频率：$\Omega_{st}$ - 通带最大衰减 (dB)：$R_p$ - 阻带最小衰减 (dB)：$A_s$

要求的参数 - 滤波器阶数：N
$$N = \dfrac{\lg \left( \dfrac{10^{0.1 A_s} - 1}{10^{0.1 R_p} - 1}\right)}{2\lg \left( \dfrac{\Omega_{st}}{\Omega_p}\right)}$$

特殊情况：$R_p = 3dB,\ \Omega_p = \Omega_c$
$$N \geq \dfrac{\lg (10^{0.1 A_s} - 1)}{2\lg \left( \dfrac{\Omega_{st}}{\Omega_p}\right)}$$

• 截止频率：$\Omega_c$
  $$\Omega_{cp} = \dfrac{\Omega_p}{\sqrt[2N]{10^{0.1R_p} - 1}} \leq \Omega_c \leq \dfrac{\Omega_{st}}{\sqrt[2N]{10^{0.1A_s} - 1}} = \Omega_{cs}$$

得到滤波器的系统函数：
$$H_a(s) = \dfrac{1}{\sqrt{1 + \left( \dfrac{s}{j\Omega_c}\right)^{2N}}}$$

记归一化原型低通滤波器的系统函数为 $H_{an}(s)$，则有：
$$H_a(s) = H_{an} = \left( \dfrac{s}{\Omega_c}\right)$$

实际应用时可以根据所求参数查表得到 $H_{an}(s)$，再去归一化得到 $H_a(s)$

切比雪夫 I 型低通滤波器

已知的参数 - 通带截止频率：$\Omega_p$ - 阻带截止频率：$\Omega_{st}$ - 通带最大衰减 (dB)：$R_p$ - 阻带最小衰减 (dB)：$A_s$

要求的参数 - 截止频率，指定 $\Omega_c = \Omega_p$

• 波纹参数：$\varepsilon = \sqrt{10^{0.1R_p} - 1}$

• 滤波器阶数：N
  $$N \geq \dfrac{\lg \left[ \sqrt{\dfrac{10^{0.1 A_s} - 1}{10^{0.1 R_p} - 1}} + \sqrt{\dfrac{10^{0.1 A_s} - 1}{10^{0.1 R_p} - 1} - 1}\right]}{\lg \left[ \dfrac{\Omega_{st}}{\Omega_p} + \sqrt{\left( \dfrac{\Omega_{st}}{\Omega_p}\right)^2 - 1}\right]}$$

由 N 和 $\varepsilon$ 查表可得 $H_{an}(s)$；由 $\Omega_c$ 去归一化可得 $H_a(s)$

模拟频域频带变换

将归一化模拟低通滤波器转换成模拟低通、高通、带通、带阻滤波器。

记归一化 $(\bar{\Omega}_p = 1)$ 模拟低通滤波器的系统函数为 $H_{an}(\bar{s})$，频率响应为 $H_{an}(j\bar{\Omega})$。
变换后各各类模拟滤波器的系统函数为 $H_a(s)$，频率响应为 $H_a(j\Omega)$。

• 带通滤波器计算步骤
  • 频带变换
    • 按上表中的公式求 $\bar{\Omega}_{p0},\ B_p,\ \bar{\Omega}_{st1},\ \bar{\Omega}_{st2}$
    • 归一化模拟低通滤波器的阻带截止频率为 $\bar{\Omega}_{st} = \min(|\bar{\Omega}_{st1}|, |\bar{\Omega}_{st2}|)$
  • 利用 $\bar{\Omega}_{p} = 1,\ \bar{\Omega}_{st},\ R_p,\ A_s$ 按照相应低通滤波器的求法求出 $H_{an}(\bar{s})$
    • 如果是巴特沃斯滤波器，当 $R_p \neq 3dB$ 时，$\Omega_p \neq \Omega_c$，需要对求出的系统函数做去归一化，得到 $H_a(\bar{s}) = H_{an}\left(\dfrac{\bar{s}}{\bar{\Omega}_c}\right)$
  • 再次利用上表中的公式，将 $\bar{s}$ 变换为 $s$ 从而得到 $H_{bp}(s)$
• 阻带滤波器计算步骤
  • 频带变换
    • 按上表中的公式求 $\bar{\Omega}_{st0},\ B_s,\ \bar{\Omega}_{p1},\ \bar{\Omega}_{p2}$
    • 归一化模拟低通滤波器的通带截止频率为 $\bar{\Omega}_{p} = \max(|\bar{\Omega}_{p1}|, |\bar{\Omega}_{p2}|)$（得到的是有关 $\bar{\Omega}_{st}$ 的式子）
    • 依据 $\bar{\Omega}_p = 1$ 计算出 $\bar{\Omega}_{st}$
  • 利用 $\bar{\Omega}_{p} = 1,\ \bar{\Omega}_{st},\ R_p,\ A_s$ 按照相应低通滤波器的求法求出 $H_{an}(\bar{s})$
    • 如果是巴特沃斯滤波器，当 $R_p \neq 3dB$ 时，$\Omega_p \neq \Omega_c$，需要对求出的系统函数做去归一化，得到 $H_a(\bar{s}) = H_{an}\left(\dfrac{\bar{s}}{\bar{\Omega}_c}\right)$
  • 再次利用上表中的公式，将 $\bar{s}$ 变换为 $s$ 从而得到 $H_{bp}(s)$

间接法设计数字滤波器

冲激响应不变法

将模拟滤波器的单位冲激响应 $h_a(t)$ 映射成数字滤波器的单位冲激响应 $h(n)$。
记抽样周期为 $T = \frac{1}{f_s}$，满足 $h(n) = h_a(nT)$。

要求： - 要求模拟滤波器是严格带限于 $\frac{f_s}{2}$，不能用于设计高通滤波器和带阻滤波器。 - 只适用于并联结构的系统函数，即系统函数必须先展开成部分分式。

计算步骤： - 计算出相应模拟滤波器的系统函数 $H_a(s)$

• 将该系统函数展开为部分分式之和的形式，即
  $$H_a(s) = \sum\limits_{k=1}^{N} \dfrac{A_k}{s - s_k}$$

• 依据 $H_a(s)$ 和抽样周期 T 得到数字滤波器的系统函数
  $$H(z) = \sum\limits_{k=1}^{N} \dfrac{A_k}{1 - e^{s_k T} z^{-1}}$$

双线性变换法

将模拟滤波器的系统函数 $H_a(s)$ 映射成数字滤波器系统函数 $H(z)$。

计算步骤： - 根据模拟角频率 $\Omega_p$、$\Omega_{st}$ 计算数字频率
$$\omega_p = \Omega_p T,\ \omega_{st} = \Omega_{st} T$$

• 计算频率预畸
  $$\Omega_p' = \dfrac{2}{T} \tan \left( \dfrac{\omega_p}{2}\right)$$
  $$\Omega_{st}' = \dfrac{2}{T} \tan \left( \dfrac{\omega_{st}}{2}\right)$$

• 根据 $\Omega_p',\ \Omega_{st}',\ R_p,\ A_s$ 计算出模拟滤波器的 $H_a(s)$

• 令 $H_a(s)$ 中
  $$s = \dfrac{2}{T} \cdot \dfrac{1 - z^{-1}}{1 + z^{-1}}$$
  从而根据 $H_a(s)$ 得到 $H(z)$

数字频域频带变换

要求将归一化模拟低通滤波器直接转换为低通、高通、带通、带阻数字滤波器。

eg. 带通数字滤波器 - 将模拟域指标变换为数字域指标 $\omega_{st1},\ \omega_{st2},\ \omega_{p1},\ \omega_{p2}$

• 求中心频率
  $$\cos(\omega_0) = \dfrac{\cos\left( \dfrac{\omega_{p2} + \omega_{p1}}{2}\right)}{\cos\left( \dfrac{\omega_{p2} - \omega_{p1}}{2}\right)}$$

• 将数字域频率指标转换，得到频域的通带截止频率和阻带截止频率

  • 选择 $\omega_p = \max(\omega_{p1}, \omega_{p2})$
  • 变换到频域
    $$\Omega = \dfrac{\cos \omega_0 - \cos \omega}{\sin \omega}$$
    
  • 取 $\Omega_{st} = \min(|\Omega_{st1}|, |\Omega_{st2}|)$

• 根据 $\Omega_p,\ \Omega_{st},\ R_p,\ A_s$ 按相应的模拟滤波器的设计方法得到 $H_{a}(s)$

  • 令 $H_a(s)$ 中
    $$s = \dfrac{1 - 2z^{-1} \cos \omega_0 + z^{-2}}{1 - z^{-2}}$$
    得到 $H_{bp}(z)$

懒得改了。。。。

FIR 滤波器

滤波器特点

• h(n) 具有对称性
  $$h(n) = \pm h(N-1-n)$$

• 群延迟为常数
  $$\tau = \dfrac{N-1}{2}$$

有四种情况： - $h(n) = h(N-1-n)$，N 为奇数：
可用于设计任一种滤波器。 - $h(n) = h(N-1-n)$，N 为偶数：
不能设计高通和带阻。 - $h(n) = -h(N-1-n)$，N 为奇数：
只能用于带通。 - $h(n) = -h(N-1-n)$，N 为偶数：
- 只能用于高通和带通。

窗函数设计法

给定理想频率响应 $H_d(e^{j\omega})$，导出 $h_d(n)$
对 $h_d(n)$ 截取有限长度，形成 $h(n)$

计算步骤

• 求参数

  • 过渡带宽：$\Delta \omega = \omega_{st} - \omega_p$

  • 截止频率：$\omega_c = \dfrac{\omega_p + \omega_{st}}{2}$

  • 阻带最小衰减：
    $$A_s = -20\lg \left( \dfrac{\delta}{1 + \delta}\right)$$
    因此给定 $A_s$ 可以得到波纹 $\delta$：
    $$\delta = \dfrac{10^{-\frac{A_s}{20}}}{1 - 10^{-\frac{A_S}{20}}}$$

  • 通带最大衰减：
    $$R_p = -20\lg \left( \dfrac{1 - \delta}{1 + \delta}\right)$$

• 求 $h_d(n)$

  • 低通滤波器
    $$h_d(n) = \left\{ \begin{aligned} &\dfrac{\sin [\omega_c (n-\tau)]}{\pi (n-\tau)},\ n \neq \tau \\ &\dfrac{\omega_c}{\pi},\ n = \tau \end{aligned} \right.$$

  • 带通滤波器
    $$h_d(n) = \left\{ \begin{aligned} &\dfrac{\sin [\omega_2 (n-\tau)] - \sin [\omega_1 (n-\tau)]}{\pi (n-\tau)},\ n \neq \tau \\ &\dfrac{\omega_2 - \omega_1}{\pi},\ n = \tau \end{aligned} \right.$$

  • 带阻滤波器
    $$h_d(n) = \left\{ \begin{aligned} &\dfrac{\sin [\pi (n-\tau)] - \sin [\omega_2 (n-\tau)] + \sin [\omega_1 (n-\tau)]}{\pi (n-\tau)},\ n \neq \tau \\ &1 - \dfrac{\omega_2}{\pi} + \dfrac{\omega_1}{\pi},\ n = \tau \end{aligned} \right.$$

  • 高通滤波器
    $$h_d(n) = \left\{ \begin{aligned} &\dfrac{\sin [\omega_c (n-\tau)]}{\pi (n-\tau)},\ n \neq \tau \\ &1 - \dfrac{\omega_c}{\pi},\ n = \tau \end{aligned} \right.$$

• 加窗截断，得到 $h(n) = h_d(n) w(n)$
  记
  $$R_N(n) = \left\{ \begin{aligned} &1,\ -\frac{N}{2} \leq n \leq \frac{N}{2} \\ & 0,\ else \end{aligned} \right.$$

  • 矩形窗
    $$w(n) = R_N(n)$$

  • 三角形窗
    $$w(n) = \left\{ \begin{aligned} &\dfrac{2n}{N-1},\quad 0 \leq n \leq \frac{N-1}{2} \\ &2 - \dfrac{2n}{N-1},\quad \frac{N-1}{2} < n \leq N-1 \end{aligned} \right.$$

  • 汉宁 (Hanning) 窗
    $$w(n) = \dfrac{1}{2}\left[1 - \cos\left( \dfrac{2\pi n}{N-1}\right)\right] R_N(n)$$

  • 海明 (Hamming) 窗
    $$w(n) = \left[0.54 - 0.46 \cos\left( \dfrac{2\pi n}{N-1}\right)\right] R_N(n)$$

  • 布莱克曼 (Blackman) 窗
    $$w(n) = \left[0.42 - 0.5 \cos\left( \dfrac{2\pi n}{N-1}\right) + 0.08 \cos\left( \dfrac{4\pi n}{N-1}\right)\right] R_N(n)$$

频率抽样设计法

基本思路

• 给定期望逼近的频率响应 $H_d(e^{j\omega})$。

• 在 $\omega$ 的一个周期 $[0, 2\pi)$ 中进行 N 点等间距抽样得到 $H(k)$，即
  $$H(k) = H_d(e^{j\omega}) |_{\omega = \frac{2\pi}{N}k},\quad k = 0, 1, \cdots, N-1$$

• 求 $h(n)$
  $$h(n) = IDFT[H(k)] = \dfrac{1}{N} \sum\limits_{k=0}^{N-1} H(k) e^{j\frac{2\pi}{N} nk},\quad n = 0, 1, \cdots, N-1$$

设计公式

PPT 上懒得打了。

计算方法：
- 在通带部分，$|H(k)| = 1$；在阻带部分，$|H(k)| = 0$；过渡带的值一般会给出。

• 通过已知的截止频率在整个周期中的占比，确定通带、阻带、过渡带各有哪几个点。

• 结合上述设计公式得到 $H(k)$

与 IIR 比较

• 可以实现严格的线性相位。
• h(n) 有限长，一定稳定。
• 相同的技术指标，FIR 所需阶数比 IIR 高得多。

第8章 网络安全

• 网络安全服务
• 密码
  • 对称密码
    • DES
    • 三重 DES
    • IDEA
    • 对称密码的性能
  • 非对称密码（公私钥密码）
    • RSA
• 数字签名与认证
  • 数字签名
  • 数据的完整性认证
    • MAC
    • 散列函数
• 典型的网络安全威胁
  • 主动攻击与被动攻击
  • 常见攻击分类
• 网络安全协议
  • 不同层次的安全协议
  • IPSec
    • 认证 (AH) 头标
    • 加密 (ESP) 头标
• 防火墙

网络安全服务

• 认证：提供某个实体的身份保护。
• 访问控制：保护资源，防止对它的非法使用和操纵。
• 数据加密：保护信息不被泄露。
• 数据完整性：保护信息以防止非法篡改。
• 不可否认性：防止参与通信的一方事后否认。

密码

密钥：参与明文密文变换的参数。

按加密模式分类： - 序列密码：位或字节加密（流密码）。
- 分组密码：将明文分成固定长度的组，用同一密钥对每一块加密，输出固定长度的密文。

按发展进程/体制分： - 古典密码：基于字符替换的密码。
- 代替密码：简单代替，多表代替，多字母或多码代替 - 换位密码：凯撒密码

• 对称密钥体制：加密密钥和解密密钥相同，也叫单钥密码体制。
  • DES（数据加密标准）
  • AES（高级加密标准）
  • IDEA（国际数据加密算法）
• 非对称密钥体制：加密密钥和解密密钥不同，也叫公钥密码体制。
  • RSA
  • 背包密码
  • 椭圆曲线
  • EIGamal
  • D_H

对称密码

加密速度快，但密钥空间大。

DES

• 在一个初始置换后，明文组被分成左半部分和右半部分，每部分 32 位。
  初始置换和初始逆置换再密码意义上作用不大，他们的作用在于打乱原来输入的 ASCII 码字划分关系，并将原来明文的校验位变成置换输出的一个字节。

• 16 轮迭代的乘积变换，称为函数 f，将数据和密钥结合起来。
  密钥有 56 位。

• 16 轮之后，左右两部分进行一次交换，再经过一个初始逆置换，算法结束。

三重 DES

使用三（或两）个不同的密钥对数据块进行三次（或两次）加密。
三重 DES 的强度大约和 112 位的密钥相当。

有四种模型： - DES-EEE3：使用三个不同密钥顺序进行三次加密变换。 - DES-EDE3：使用三个不同密钥一次进行加密-解密-加密变换。 - DES-EEE2：密钥 K1=K3，顺序进行三次加密变换。 - DES-EDE2：密钥 K1=K3，依次进行加密-解密-加密变换。

IDEA

64 位大小的分组加密算法，密钥长度为 128 位，加密成 64 位密文。

加密密钥和解密密钥不同，但是从一个主密钥派生出来，因此仍是对称的加密体制。

对称密码的性能

• 安全性能
  • 密钥长度：对 n 位的密钥，若密码系统是对称的，则需要计算 $2^{n-1}$ 次。
  • 分组长度
  • 轮数
  • 密钥编排函数
• 实现性能
  • 计算
  • 内存利用

非对称密码（公私钥密码）

密钥分发简单，需要保存的密钥减少，但加密速度慢。
可用于数字签名和密钥分发。

RSA

计算过程： - 密钥的生成 - 选择 p、q（p、q 为互异素数）
计算 $n = p \cdot q,\ m = (p-1)(q-1)$ - 选择整数 e 与 m 互素，即 $gcd(m, e) = 1, 1 < e < m$
gcd 表示最大公约数。 - 计算 d，使 $(e \cdot d) \mod m = 1$
公钥 Pk = {e, n}，私钥 Sk = {d, n}

• 加密（使用 Pk）
  • 明文是以分组方式加密的，每一个分组的比特数应小于 n 的二进制表示，即每一个分组的长度应小于 $\log_2 n$
  • 明文 M < n，密文 $C = M^e \mod n$
• 解密（使用 Sk）
  • 密文 C，明文 $M = C^d \mod n$

eg.
p = 3, q = 11
$n = 3 \times 11 = 33,\ m = 2 \times 10 = 20$
选 e = 3，则 $3d \mod 20 = 1$，解得 $d = 7$。
对明文 M = 2，得到密文 $C = 2^3 \mod 33 = 8$
对密文解密可得明文 $M = 8^7 \mod 33 = 2$

安全分析：
选取的素数 p、q 要足够大，则分解给定乘积 n 再计算上是不可行的。
基于短期安全性考虑，n 的长度至少应为 1024 比特；而长期安全性要求 n 的长度这至少为 2048 比特。

数字签名与认证

数字签名

利用私钥生成签名，用公钥验证签名。
一个数字签名方案是由签名算法和验证算法组成。

• 签名算法利用私钥生成签名。
  称消息 m 的签名为 sig(m)，然后将 (m, sig(m)) 发给接收方。

• 由于无法识别数字签名与其拷贝之间的差异，所有在数字签名前应加上时间戳。

• 验证算法利用签名者的公钥对 sig(m) 进行解密，如果解密输出与 m 一致，则为合法数据。

数字签名的目标： - 接收方可以验证发送方声称的身份。 - 发送方不能否认该消息的内容。 - 接收方不可能自己编造这样的信息。

数据的完整性认证

可用于做认证的函数： - 加密函数 - 用对称密钥加密，信息的完整作为对信息的认证； - 用公钥密码中的私钥加密（即签名），但加密速度太慢。 - 消息认证码 (MAC)
对信源消息的一个编码函数。 - 散列函数
将任意长的信息映射成一个固定长度的信息。

MAC

• 利用函数 f 和密钥 k，将要发送的明文 x 或密文 y 变换成 r bit 的消息认证码 f(k, x)（或 f(k, y)）。

• 将其称为认证符附加在 x（或 y）之后发出。

• 接收者收到发送的消息序列后，按发送方同样的方法对接收的数据（或解密后）进行计算，得到相应的 r bit 数据。

散列函数

单向散列函数 (hash) 是 MAC 的一种变形，从一段很长的报文中计算出一个固定长度的比特串，用于消息的完整性验证。

单向散列函数有以下特征： - 给定任意长度的 P，易于计算处固定长度的 H(p)。 - 只给出 H(p)，几乎无法找出 P。 - 对于任意给定的 X，找到满足 H(Y) = H(X) 的 Y($\neq x$) 在计算上是不可行的（抗弱碰撞）。 - 找到满足 H(Y) = H(X) 的任意一对 (X, Y) 在计算上是不可行的（抗强碰撞）。

认证方法： - 消息：X，任意比特 - 消息摘要：Z = H(X)，160 比特 - 签名摘要：$Y = sig_k (Z)$

标准：MD5（128比特），SHA-1（160比特）等。

典型的网络安全威胁

主动攻击与被动攻击

主动攻击更改数据流，或伪造假的数据流。
有以下四种形式： - 伪装：即冒名顶替。一般而言，伪装攻击的同时往往还伴随着其他形式的主动攻击。 - 重放：先被动地窃取通信数据，然后再有目的地重新发送。 - 篡改：即修改报文的内容。或者对截获的报文延迟、重新排序。 - 拒绝服务：阻止或占据对通信设是的正常使用或管理。针对特定目标或某个网络区域。

被动攻击对传输进行偷听与监视，获得传输信息。
有以下两种形式： - 报文分析：窃听和分析所传输的报文内容。 - 流量分析：分析通信主机的位置、通信的频繁程度、报文长度等信息。

常见攻击分类

• 社会工程：攻击者可通过各种社交渠道获得有关目标的结构、使用情况、安全防范措施等有用信息从而提高攻击成功率。
• 口令破解：攻击者可通过获取口令文件，然后运用口令破解工具获得口令，也可通过猜测或窃听等方式获取口令。
• 连接盗用：在合法的通信连接建立后，攻击者可通过阻塞或摧毁通信的一方来接管已经过认证建立起来的连接，从而 假冒被接管方与对方通信。
• 网络窃听：网络的开放性使攻击者可通过直接或间接窃听获取所需信息。
• 数据篡改：攻击者可通过截获并修改数据或重放数据等方式破坏数据的完整性。
• 地址欺骗：攻击者可通过伪装成被信任的IP 地址等方式来骗取目标的信任。
• 恶意扫描：攻击者可编制或使用现有扫描工具发现目标的漏洞，进而发起攻击。
• 基础设置破坏：攻击者可通过破坏 DNS 或路由信息等基础设施，使目标陷于孤立。
• 数据驱动攻击：攻击者可通过施放病毒、特洛伊木马、数据炸弹等方式破坏或遥控目标。
• 服务拒绝：攻击者可直接发动攻击，也可通过控制其它主机发起攻击，使目标瘫痪。如发送大量的数据洪流阻塞目标。

网络安全协议

不同层次的安全协议

• 链路层：链路隧道协议、加密技术
• 网络层：IPSec 协议
• 传输层：SSL 协议
  在 TCP 协议之上为两个端实体之间提供安全通道的协议。
• 应用层：SHTTP、PGP、S/MIME

IPSec

• 传输模式：用来保护某个 IP 净荷的上层协议。
• 隧道模式：在两个网关之间保护整个 IP 分组。
  会更换新的 IP 头标 (?)

认证 (AH) 头标

提供数据完整性保护，抗重播攻击。

安全组合 (SA)：为使通信双方的认证/加密算法一致，相互间建立的联系。

IP 头标 + AH 头标 + TCP/UDP 头标 + 用户数据
认证范围包括上述全部。

AH 头标包含： - 下一个头：8 bit - 净荷长度：8 bit
- 保留：16 bit - 安全参数索引 (SPI)：32 bit
将目的 IP 地址和 SPI 组合即可确定 SA。 - 序列号：
利用该域抵抗重播攻击。 - 认证数据：长度可变，为 32 bit 的整数倍
具体格式因认证算法而异。

加密 (ESP) 头标

提供数据机密性、完整性保护，抗重播攻击。

IP 头标 + ESP 头标 + TCP/UDP 头标 + 用户数据 + ESP 尾标 + ESP（认证数据）

• 认证范围：ESP 头标到 ESP 尾标。
• 加密范围：TCP/UDP 头标到 ESP 尾标。
• ESP 净荷：TCP/UDP 头标 + 用户数据

防火墙

防火墙是在两个网络之间强制实行访问控制策略的由软硬件构成的系统。

功能： - 过滤不安全的服务和禁止非法访问。 - 控制对特殊站点的访问，可以允许受保护网络的一部分主机被外部访问，而其它部分则禁止。 - 提供访问记录和审计等功能。

分类： - 包过滤防火墙：仅根据分组中的信息（地址、端口号、协议）执行相应的过滤规则，每个分组的处理都是独立的。 - 状态检测防火墙：不仅根据分组中的信息，而且还根据记录的连接状态、分组传出请求等来进行过滤。
TCP：为建立连接的SYN分组建立状态，只允许对该SYN的应答分组进入。连接建立后，允许该连接的分组进入。 - 代理型防火墙：通过对网络服务的代理，检查进出网络的各种服务。

第7章 应用层

• 网络的计算和访问模式
• 域名系统 (DNS)
  • DNS 元素
  • 域名查询算法
• 文件服务 (FTP)
  • 主动模式
  • 被动模式
• 电子邮件
  • 邮件发送过程
  • SMTP
  • POP3
• HTTP

网络的计算和访问模式

• 以大型机为中心的计算模式：分时共享模式 (time-sharing)

  特点：许多用户共享 CPU 资源和数据存储功能，终端只用于命令的输入和结果的显示。

• 以服务器为中心的计算模式：资源共享模式 (resource-sharing)

  特点：共享共同的应用，如文件服务器、打印服务器。

• 客户端/服务器模式 (Client/Server)

  特点：系统使用了客户和服务器双方的资源和计算能力来执行一个特定的任务。

  应用：前端（即客户部分）/ 后端（服务器部分）。

  缺点：单点失效、性能瓶颈（计算、存储资源受限，网络拥塞等）。

• 对等模式 (Peer to Peer, P2P)

  特点：用户和资源处于对等状态，分布式计算和存储（客户的加入退出会影响性能）。

  是一个应用型网络，一般由网络边缘节点构成，充分利用资源。

  与 C/S 模型相比，优点有：

  • 减轻了服务器的计算压力，消除了对某个服务器的完全依赖，可以将任务分配到各个节点上，因此大大提高了系统效率和资源利用率。
  • 多个客户机之间可以之间共享文档。
  • 可扩展性好。
    传统服务器有响应和带宽限制，因此只能接收一定数量的请求。
  • 网络健壮性强，单个节点的失效不会影响其他部分节点。

  需要解决的问题：动态性，安全性，可管理性等。

• 云计算模式

  以网络为中心的计算模式，虚拟化的资源。

域名系统 (DNS)

域名：标识网络上的主机，与 IP 地址对应。
一台主机可以有多个域名，一个域名可以对应多个 IP 地址。

eg.
www.baidu.com - com：顶级域名 - baidu：二级域名 - www：三级域名

DNS 元素

• 解析器 (resolver)：查询域名的应用程序或者库函数调用。
• 域名空间：所有可能的域名集合。
• 资源记录：与域名相关联的信息，包括 IP 地址等。
  常见的资源记录如下：
  • A (ADDR)：IP 地址。
  • MX ：邮件交换，准备接收邮件地址的主机名字。
  • NS (NAMES)：名字服务器。 存放资源记录，实现域名到 IP 地址的解析，也称为 DNS 服务器。

DNS 报文传输层可采用 TCP 或 UDP 协议，端口号为 53 号。

域名查询算法

• 递归查询 (recursive query)：

  每一个被请求的域名服务器如果没有该记录，它就向其他域名服务器查询，并沿查询路径逐个返回记录。

  主机向本地域名服务器的查询采用的是递归查询。

• 迭代查询 (iterative query)：

  本地域名服务器如果没有该记录，就向高级域名服务器请求，被请求的服务器如果没有该记录就返回一个可供查询的域名服务器地址。即最终是向有信息的服务器直接查询地址。

  本地域名服务器向根域名服务器的查询采用迭代查询。

文件服务 (FTP)

目的：文件传送。

控制连接：TCP 21 端口，一直打开。
数据连接：TCP 20 端口，根据需要打开。

主动模式

主动模式下， FTP 客户端从任意端口 N (> 1023) 连入到 FTP 服务器的命令端口 21。
然后客户端在 N+1 端口监听来自服务器 20 端口的数据连接。

被动模式

被动模式下，客户端从任意端口 N (> 1023) 向服务器的 21 端口发送 PASV，服务器返回数据通道的端口号 M。
然后客户端在 N+1 端口监听来自服务器 M 端口的数据。

电子邮件

消息交换的协议： - 简单邮件传输协议 (SMTP)：推送协议，用于发送邮件 - 邮局协议第 3 版 (POP3)：拉取协议，用于读取邮件 - Internet 消息访问协议 (IMAP)：拉取协议

消息格式的协议： - 基本的 ASCII 的文本邮件 - 多用途 Internet 邮件扩展 (MIME)

邮件发送过程

• 发信人调用用户代理来编辑要发送到 receipt@abc.com 的邮件。
  用户代理用 SMTP 把邮件传送给预先设置的发送邮件服务器。

• 发送邮件服务器将邮件放入邮件缓存队列中，等待发送。

• 发送邮件服务器的 SMTP 客户进程，发现有待发送的邮件，向接收方邮件服务器的 SMTP 服务器进程发起 TCP 连接。

• TCP 连接建立后，SMTP 客户进程开始向远程的 SMTP 服务器进程发送邮件。
  当待发送邮件发送完，SMTP 就关闭建立的连接。

• 运行在接收方邮件服务器中的 SMTP 服务器进程收到邮件后，将邮件放入接收方的用户邮箱中，等待接收方在方便时进行读取。

• 接收方在打算收信时，调用客户代理，使用 POP3（或 IMAP）协议将自己的邮件从接收方邮件服务器的用户邮箱中取回。

SMTP

SMTP 规范两个相互通信的 SMTP 进程之间应如何交换信息。

传输层采用 TCP 协议，25 号端口。

SMTP 采用客户/服务器方式，发送邮件进程是 SMTP 客户，接收邮件进程是 SMTP 服务器。

SMTP 采用简单的 ASCII 消息，在多媒体、加密传输中存在问题：
MIME 可以对 SMTP 进行扩展，使得非 NVT ASCII 数据能够通过邮件发送。

SMTP 以明文方式传输，缺少认证，安全上存在不足：
带扩展的 SMTP (ESMTP)

POP3

邮局协议 POP 是一个简单、功能有限的邮件读取协议。

传输层采用 TCP 协议，端口 110。

IMAP 是 POP3 的改进，运行在 143 端口，主要区别在于： - POP3 下载到用户代理所在的计算机上，用户难以在不同的计算机上阅读。 - IMAP 存储在邮件服务器，客户本机 IMAP 客户端操作与邮件服务器同步。

HTTP

万维网 (WWW)。
web 页面的编写采用 HTML 语言，传送采用 HTTP 协议，观看通过浏览器。

WWW 的特点： - 将资源按对象进行分类。 - 采用超文本技术，将菜单嵌入文本中。 - 采用超媒体技术，能检索和浏览非文本信息。 - 采用超链接技术，用户可以访问一个又一个文档。

统一资源定位符 (URL)：用于命名万维网上的各种 web 页面。
URL 的一般形式：<协议>：//<主机域名>:<端口>/<路径及文件名>

HTTP（超文本传输协议）采用 80 端口建立客户/服务器端的 TCP 连接。
在 HTTP 1.0 中，连接建立后只发送一个请求-响应后，连接就释放。
HTTP 1.1 支持持续连接（也叫连接重用），连接建立后，在其上发送多个请求-响应，降低连接开销。

HTML（超文本标记语言）允许在页面中包含文本、图像和指向其它 web 页面的超链接等。

web 文档种类： - 静态文档：HTML 文件，存在服务器中。 - 动态文档：请求时由服务运行程序或脚本来创建。 - 活动文档：在客户端活动的程序。

WWW 工作过程： - 用户在浏览器的地址栏键入 URL，或者点击某个超链接对应的 URL。 - 浏览器分析 URL 的主机域名，通过 DNS 系统找到资源所在的主机及 web 服务器的 IP 地址。 - 浏览器与 web 服务器的 80 端口建立 TCP 连接。 - 向 web 服务器发出 HTTP 请求消息，要求获得某个页面。 - web 服务器通过 HTTP 响应消息传送页面。 - 释放 TCP 连接，浏览器在本机上显示页面。

第6章 传输层

• 传输服务
  • Berkeley 套接字
    • TCP & UDP 套接字编程实现
• 传输协议的要素
  • 寻址
    • 利用 TSAP 传输消息
    • TSAP 获取方法
  • 连接
    • 建立连接：三次握手
    • 释放连接
  • 流量控制 & 拥塞控制
    • 流量控制
    • 理想带宽分类
    • 调整发送速率
• Internet 传输协议
  • UDP
    • 头标
    • 应用
  • TCP
    • 服务模型
    • 特点
    • 头
    • 连接建立
    • 连接释放
    • 连接管理模型
    • 滑动窗口
    • 计时器管理
    • 拥塞控制

传输服务

传输层所处的地位： - 面向信息处理：
应用层 - 面向传输：
传输层、网络层、数据链路层、物理层

• 用户功能：
  应用层、传输层
• 网络功能：
  网络层、数据链路层、物理层

传输层向应用层提供传输服务，属于面向传输部分的最高层。
同时传输层也是用户功能中的最低层，为应用层屏蔽任何与网络有关的操作。
传输层协议是端到端的。

传输层实现在不同主机上的进程之间的通信，每个应用进程都至少与一个传输层地址（端口）相关联。

向上层提供的服务：面向连接的传输服务和无连接的传输服务。

传输实体之间发送的消息：段 (segment) 或传输协议数据单元 (TPDU)。 - 段（传输层）被包裹在数据包（网络层）中，而数据包被包含在帧（数据链路层）中。

• 当一帧到达时，数据链路层对帧头进行处理，如果帧目标地址与本地传递地址匹配，则把帧的有效载荷字段中的内容传递给网络实体。
  网络实体再对数据包头进行类似处理，然后把数据包的有效载荷字段内容向上传递给传输实体。

Berkeley 套接字

套接字 (socket)

• 服务器：依次执行 SOCKET、BIND、LISTEN、ACCEPT。
• 客户端：不需要 BIND，依次执行 SOCKET、CONNECT。
• 连接建立后，双方都可以使用 SNED、RECV 收发数据。
• 数据传输结束后，双方使用 CLOSE 释放连接。

TCP & UDP 套接字编程实现

TCP: - 服务器依次执行 - socket - bind - listen - accept - 此时可以接收客户端发来的连接请求 - recv、send - closesocket

• 客户端依次执行
  • socket
  • connect
    • 在服务器执行 accept 之后
  • send、recv
  • closesocket

UDP: - 服务器依次执行 - socket - bind - recvfrom、sendto - 在 recvfrom 调用后，服务器保持等待，直到从客户端收到数据报。 - 由于没有事先 connect，故每次收发数据都需要附上接收/发送地址。

• 客户端依次执行
  • socket
  • sendto、recvfrom
  • closesocket

传输协议的要素

寻址

当一个应用进程希望与另一个远程应用进程建立连接时，必须指定要连接到哪个应用进程上，即指定对方的传输服务访问点 (TSAP)。
网络层上也有类似端点，称为网络服务访问点 (NSAP)，而无连接的网络层不需要提供 NSAP。IP 地址是 NSAP 的实例。

一个全局唯一的传输服务用户由 {主机地址，NSAP，TSAP} 表示，称为端点地址。

在 TCP/IP 中，NSAP 可略去，TSAP 称为端口号。
以 {IP 地址，port，协议类型} 唯一标识传输服务的用户。
{源/目的 IP 地址，源/目的端口号，协议类型} 五元组标识一个数据流。

利用 TSAP 传输消息

• 主机 2 上的邮件服务进程将自己关联到 TSAP 1522 上，等待入境连接请求的到来。

• 主机 1 上的应用进程希望发送一个邮件消息，于是把自己关联到 TSAP 1208 上，并发出一个 CONNECT 请求。
  该请求指定主机 1 上的 TSAP 1208 作为源，主机 2 上的 TSAP 1522 作为目标。
  这个动作在应用进程和服务器之间建立了一个连接。

• 应用进程发送邮件消息。

• 作为响应，邮件服务器表示它将传递该消息。

• 传输连接被释放。

TSAP 获取方法

• 服务进程固定在特定的 TSAP 地址上。

  只适用于少数永不改变的关键服务。

• 采用端口映射器/名字服务器。

  用户与端口映射器建立一个连接。
  用户通过这个连接发送一条消息指定它想要的服务名字；端口映射器返回相应的 TSAP 地址。
  之后用户释放与端口映射器之间的连接，与所需的服务建立一个新连接。

  当一个新的服务被创建时，它必须向端口映射器注册，把它的服务名字与 TSAP 地址告诉端口映射器。端口映射器将该信息记录到它的内部数据库中。

• 采用初始连接协议。

  每台希望向远程用户提供服务的机器有一个特殊的进程服务器充当不那么频繁使用的服务的代理。

  进程服务器在同一时间监听一组端口，等待连接请求的到来。
  用户发出一个连接请求，并指定所需服务的 TSAP 地址。如果该 TSAP 地址上没有服务器正在等着，则用户得到一条与进程服务器的连接。
  在获取入境请求后，进程服务器派生出被请求的服务器，允许该服务器继承与用户的现有连接。新服务器完成要求的工作，而进程服务器继续回去监听新的连接要求。

  只适用于服务器可按需创建的场合。

连接

对于面向连接的传输服务，首先要和对端的对等实体建立连接。

传输层连接本质上是在发送端和接收端上为实现可靠船速而维护的一些参数状态。 - 发送/确认序列号的维护，发送/接收窗口的管理，接收端缓存大小等 - 各种计时器

数据传输完毕还需要释放连接，即释放维护连接参数的缓存。

建立连接：三次握手

正常情况：

• 主机 1 选择一个序号 x，并向主机 2 发送包含该序号的连接请求 CR (seq = x)。

• 主机 2 应答连接确认 ACK (seq = y, ACK = x)，其中包含确认号 x 和序列号 y。

• 主机 1 在其发送的第一个数据中采用序列号为 x，并确认主机 2 的序列号 x，即发送 DATA (seq = x, ACK = y)。

出现旧的重复 CR：

• 主机 2 收到旧的 CR (seq = x)，而主机 1 并不知情。
  主机 2 回复 ACK (seq = y, ACK = x)。

• 主机 1 拒绝连接请求，即发送 REJECT (ACK = y)。
  主机 2 放弃连接。

出现旧的重复 CR 和 ACK：

• 主机 2 收到旧的 CR (seq = x)，而主机 1 并不知情。
  主机 2 回复 ACK (seq = y, ACK = x)。

• 主机 2 收到旧的 DATA (seq = x, ACK = z)。
  主机 2 根据确认是 z 而不是 y 知道这是一个旧确认包，因此不会建立连接。

• 主机 2 收到 主机 1 发送的 REJECT (ACK = y)，于是放弃连接。

释放连接

非对称释放：连接的任何一方都可以断开整个连接。

可能会导致数据的丢失。
如：主机 1 发送 DATA，它正确到达主机 2；主机 1 再次发送 DATA，但在到达之前主机 2 发出了 DISCONNECT；因此连接被释放，但数据丢失了。

对称释放：把连接看作是由两个单独的单项连接，并要求单独释放每一个单项连接。 - 正常情况

• 主机 1 发送释放连接请求 DR 并启动一个计时器，但它不立即拆除连接，而是等待对方确认。

• 主机 2 收到 DR 后也发回一个 DR，并启动一个计时器。

• 当主机 1 收到主机 2 发送的 DR 后，它会返回一个 ACK 段并释放连接。

• 主机 2 收到 ACK 后，它也释放连接。

• 最后一个 ACK 丢失

  通过主机 2 的计时器来补救。
  如果在计时器超时前，主机 2 没有收到 ACK；则计时器超时后，主机 2 无论如何都释放连接；此时主机 1 已经释放了连接。

• 主机 2 发送的 DR 丢失

  通过主机 1 的定时器来补救。
  如果在定时器超时前，主机 1 没有收到来自主机 2 的 DR；则计时器超时后，主机 1 再次发送 DR。

流量控制 & 拥塞控制

流量控制

流量控制：根据接收端的缓存容量来动态地调整发送端的窗口大小，避免一个快速的发送端淹没一个慢速的接收端。

采用滑动窗口协议，但是使用可变大小的动态缓冲区，即一个可变大小的窗口。

• 初始时，发送端根据它期望的需求要求一定数量的缓冲区。
• 接收端根据它的能力尽可能多的缓冲区。
• 每次发送端传输一段，它必须减少分配给它的缓冲区数。
• 当分配给发送端的缓冲区数达到 0 时，完全停止发送。
• 接收端在逆向流量中捎带上单独的确认和缓冲区数。
  • TCP 采用这种模式，将缓冲区的分配捎带在头的 Windows size 字段。

为了避免控制段丢失造成的死锁，每台主机应该定期地在每个连接上发送控制段，给出确认和缓冲区状态。

理想带宽分类

功率定义： $$功率 = \dfrac{负载}{延迟}$$ 功率最初随着提交负载的上升而上升，延迟仍然很小并且基本保持不变；
但随着延迟快速增长，功率达到最大，然后开始下降。
达到最大功率的负载表示了传输实体放置在网络上的有效负载。

最大-最小公平：如果分配给一个流的带宽在不减少分配给另一个流带宽的前提下无法得到进一步增长，那么就不给这个流更多带宽。

拥塞控制：根据网络的承载容量来动态地调整发送端的窗口大小，避免发送端发送的数据超过了网络容量。
拥塞控制时网络层和传输层的共同责任。
一个良好的拥塞控制算法，应迅速收敛到理想的操作点，并跟踪这随时变化的操作点。

调整发送速率

发送速率可能受到两个方面因素的限制： - 在接收端没有足够缓冲区的情况下，进行流量控制。 - 在网络容量不足的情况下，进行拥塞控制。

显示拥塞协议 (XCP)
TCP 采用显示拥塞通知 (ECN)：
路由器在经历拥塞的数据包中设置警告比特来警告发送端放慢速率，但它们不告诉源端该减缓多少。

增加或减少速率的方式由控制法则决定。
其中加法递增乘法递减 (AIMD) 法则是达到有效和公平操作点的适当流量规则：
用户加法递增他们的带宽，然后当收到拥塞信号时乘法递减他们的带宽。

Internet 传输协议

UDP

用户数据报协议 (UDP)：提供无连接的服务。

头标

UDP 传输的段（数据报）由 8 字节的头和有效载荷字段构成。 - 源端口：2 字节。

• 目标端口：2 字节。

• UDP 长度：2 字节。

  包含 8 字节的头和数据两部分的总长度。
  最小长度是 8 字节，刚好覆盖 UDP 头。
  最大长度是 65515 字节。因为 IP 头的总长度字段为 16 位，最大长度为 65535 字节；而 IP 头最少需要 20 字节。

• UDP 校验和（可选）：2 字节

  校验 UDP 头、数据和一个概念性的 IP 伪头。

  IPv4 伪头包括：

  • 4 字节源地址
  • 4 字节目的地址
  • 1 字节 0
  • 1 字节 UDP 的协议号 17
  • 2 字节 UDP 长度（包括头，以字节为单位）

  与 IP 头中的头校验和算法类似。
  计算校验和时：

  • 当数据字段的长度为奇数字节时，则在数据字段填充一个额外的 0 字节（因为要以 16 位为单位计算校验和）。
  • 当结果为全 0 时，将校验和置为全 1。
  • 如果发送端没有计算校验和，则将该字段置为 0。 验算时的步骤也和 IP 头校验和的验算类似，只是求和范围改成上述 UDP 的校验范围。

应用

• 具有简单高效的特点。

• 客户-服务器模式应用，如域名系统 (DNS)。

• 话音、视频等实时多媒体应用。

TCP

传输控制协议 (TCP)：在不可靠的互联网络上提供可靠的端到端字节流的传输协议。

服务模型

TCP 服务由发送端和接收端创建套接字来获得。 - 每个套接字有一个套接字编号（地址），该编号由主机的 IP 地址以及一个本地主机的 16 位数值（端口，TCP 的 TSAP 名字）。

• 一个套接字有可能同时被用于多个连接，即两个或多个连接可能终止于同一个套接字。

• 每个连接可以用两端的套接字标识符来标识，即 (socket1, socket2)。

知名端口：1024 以下的端口号被保留，只能用作由特权用户启动的标准服务。 | 端口 | 协议 | 用途 | | ---- | ---- | --- | | 20、21 | FTP | 文件传输 | | 22 | SSH | 远程登录 | | 23 | Talnet | 远程登录 | | 25 | SMTP | 电子邮件 | | 80 | HTTP | 万维网 |

特点

• 字节流传输，端到端之间不保留消息的边界。

• TCP 连接上的每个字节都有独有的 32 位序号，起始编号随机。

• 全双工，一个连接上传输两个方向的 TCP 数据，各自的编号是独立的。

• 点到点，不支持组播或广播传输模式。

• 发送端和接收端的 TCP 实体以段的形式交换数据。
  TCP 段由一个固定的 20 字节的头（加上可选的部分）以及随后的 0 个或多个数据字节构成。
  有两个因素限制了段的长度：

  • 包括 TCP 头在被的每个段，必须适合 IP 的 65515 个字节有效载荷。
  • 每个网络有最大传输单元 (MTU)。

• 使用具有动态窗口大小的滑动窗口协议。
  发送端每次发送的数据量由发送窗口大小决定，而不是以应用层递交的消息为单位；
  接收端每次向上层递交的数据量由落在接收窗口中并且有序的数据决定。

• 可靠，具有流量控制和拥塞控制。

  • 发送端：超时重传。
  • 接收端：发送确认，缓存处理乱序。

头

每个段的起始部分是一个固定格式的 20 字节头。
固定的头部之后可能有头的选项。
选项之后是最多可达 $65535 - 20 - 20 = 65495$ 个字节的数据。（其中第一个 20 指 IP 头，第二个 20 指 TCP 头。

没有任何数据的 TCP 段也是合法的，通常被用作确认和控制消息。

• 源端口 (Source port)：16 位

• 目的端口 (Destination port)：16 位

• 序号 (Sequence number)：32 位
  标识本报文段的第一个字节在数据流中的位置。

• 确认号 (Acknowledgment number)：32 位
  标识本段报文段的发送方下一个期待接收的字节编号。
  是累计确认，用一个数字概括了接收到的所有数据。

• TCP 头长度 (TCP header length)：4 位
  指明 TCP 头的长度，以 32 位字为单位。

• 保留 (Reserved)：4 位
  置 0。

• 标志位：共 8 位，每个标志位 1 位

  • CWR & ECE：用于显示拥塞通知。
    当 TCP 接收端收到了来自网络的拥塞指示后，就设置 ECE 以便给 TCP 发送端发 ENC-Echo 信号，告诉发送端放慢发送速率。
    TCP 发送端设置 CWR，给接收端发 CWR 信号，告诉接收端已放慢发送速率，无需继续发送 ENC-Echo 信号。

  • URG：置 1 时，紧急指针有效。

  • ACK：置 1 时，指示确认段有效。

  • PSH：置 1时，指出这是被推送的数据。
    请求接收端一旦收到数据后立即将数据递交给应用程序。

  • RST：连接复位。
    用于拒绝不存在的端口连接请求、中止异常连接等。

  • SYN：用于建立连接过程。
    在连接请求中，(SYN = 1, ACK = 0)，表明该段没有使用捎带确认字段。
    在连接应答中，捎带了一个确认，因此 (SYN = 1, ACK = 1)。

  • FIN：用于释放连接。

• 窗口大小 (Window size)：16 位。
  指定在已确认的字节之后还可以接收的字节数。
  窗口大小为 0 标识希望对端不再发送数据，用于流量控制。

• 校验和 (Checksum)：16 位。
  与UDP 的校验和类似，只是 IP 伪头中的协议号为 TCP 的协议号 6。

• 紧急指针 (Urgent pointer)：16 位
  指向紧急数据的结束位置（相对于序列号的偏移量）。

• 选项 (Options)：0 或 32 位的倍数，不足部分用 0 填充 对于最长的 TCP 头，选项可以扩展到 40 个字节。

连接建立

使用三次握手法来建立连接。
通过三次握手，主机 1 和主机 2 之间完成初始序列、窗口大小（扩大因子）、最大数据段尺寸等参数的协商，并且分配连接所需要端点资源。

正常情况： - 主机 1 发送请求连接数据段（SYN 数据段）：
SYN 标志置 1，ACK 标志置 0，选择初始序列号 SEQ = x。
即发送 SYN (SEQ = x)。
SYN 数据段不携带任何数据，但要消耗一个字节的序号。

• 主机 2 响应连接确认数据段（SYN+ACK 数据段）：
  SYN 标志置 1，ACK 标志置 1，选择初始序列号 SEQ = y；并对 x 进行确认，设置 ACK = x + 1。
  即发送 SYN (SEQ = y, ACK = x +1)。
  SNY+ACK 数据段也不携带数据，但消耗一个字节的序号。

• 主机 1 响应连接确认数据段：
  ACK 标志置 1，序列号 SEQ = x + 1；并对 y 进行确认，设置 ACK = y + 1。
  即发送 (SEQ = x + 1, ACK = y + 1)。
  ACK 数据段如果不携带数据就不消耗序号。

两端同时建立连接： - 主机 1 发送 SYN (SEQ = x)，同时主机 2 发送 SYN (SEQ = y)。

• 主机 2 收到消息后发送 SYN (SEQ = y, ACK = x + 1)，主机 1 收到消息后发送 SYN (SEQ = x, ACK = y + 1)。

• 实际上只建立了一个连接，并不是两个。

连接建立失败： - 主机 1 请求连接数据段（SYN 数据段）

• 主机 2 的 TCP 实体检查是否有进程已经在目标端口字段指定的端口上执行了 LISTEN。
  如果没有，则它发送一个设置了 RST 的应答报文，拒绝主机 1 的连接请求。

连接释放

TCP 的全双工连接可以看成一个双单工的连接，每个单工连接都独立地释放。

通常情况下，释放一个连接需要 4 个 TCP 段：
通信双方都必须向对方发送 FIN = 1 的 TCP 段并得到对方的应答，即每个方向上一个 FIN 和一个 ACK。
然而，第一个 ACK 和第二个 FIN 有可能被组合在同一个段中，从而将所需段总数降低到 3 个。
主机发送 FIN 数据段后，就不再向对方发送数据。

为防止半连接，必须使用定时器计时，对 FIN 数据段的应答在两个最大分组生命期内未到达，则发送端释放连接，对方也会因为超时释放。

连接管理模型

建立连接和释放连接所需的步骤可以用一个具有 11 个状态的有限状态机来表示。
每一种状态中，都存在特定的合法事件。当一个合法事件发生时，可能需要采取某个动作；当发生其他事件时，则报告一个错误。

建立连接过程： - 客户端和服务器都是从 CLOSED 状态开始。

• 客户端：应用程序发出 CONNECT 请求，本地的 TCP 实体创建一条连接记录，并将它标记为 SYN SENT 状态，然后发送一个 SYN 段。
  • 在 SYN SENT 状态中，客户端等待服务器的 SYN+ACK 字段
• 服务器：收到来自客户端的 SYN 后，创建一条连接记录，将其标记为 SYN RCVD 状态，然后发送一个确认（即 SYN+ACK 段）。
  • 在 SYN RCVD 状态中，服务器等待来自客户端的最后一个 ACK。
• 客户端：收到来自服务器的 SYN+ACK 段后，发出三次握手中的最后一个 ACK 段，然后切换到 ESTABLISHED 状态。
  • 在 ESTABLISHED 状态中，连接已建立，双方可以进行数据传输。
• 服务器：收到来自客户端的 ACK 段后，进入 ESTABLISHED 状态，连接建立完成。

释放连接过程： - 客户端和服务器都是从 ESTABLISHED 状态开始。

• 客户端：应用结束，执行 CLOSE 原语。本地的 TCP 实体发送一个 FIN 段，将当前状态设置为 FIN WAIT1，等待对应的 ACK。
  • 在 FIN WAIT1 状态下，客户端等待服务器的 ACK 和 FIN。
• 服务器：收到客户端的 FIN 段，发送 ACK 段，并进入 CLOSE WAIT 状态。
  • 在 CLOSE WAIT 状态下，服务器等待应用程序的 CLOSE 操作，同时允许继续接收来自客户端的数据。
• 客户端：收到 ACK，状态迁移到 FIN WAIT2，并且连接的一个方向被关闭。
  • 在 FIN WAIT2 状态下，客户端等待来自服务器的 FIN。
• 服务器：执行 CLOSE，TCP 实体向客户端发送一个 FIN 段，并进入到 LAST ACK 状态。
  • 在 LAST ACK 状态下，服务器等待来自客户端的 ACK。
• 客户端：收到来自服务器的 FIN 段，发送 ACK 段，进入 TIME WAIT 状态。
  • 在TIME WAIT 状态下，TCP 要等待一段长度为最大数据包生存期两倍的时间。
    以便确保在该阶段收到所有可能延迟或重复的数据包，并正确处理，避免对后续连接产生干扰。
    
  • 计时器超时后，TCP 删除该连接记录，并进入 CLOSED 状态。
• 服务器：收到来自客户端的 ACK 段，同样等待长度为最大数据包生存期两倍的时间后，释放该连接并删除相应的连接记录，进入 CLOSED 状态。

滑动窗口

TCP 采用可变大小的动态缓冲区，缓冲区的大小由数据包头中的 Window size 指定。

特点： - 可靠有序的传输：使用发送缓存和接收缓存，只有被确认窗口才滑动。

• 流量控制：接收端根据可用剩余缓冲区来指定窗口大小。

• 采用延迟确认：将确认和窗口更新消息延迟发送，希望通过捎带技术节约带宽。

eg. 假设接收端有一个 4096 字节的缓冲区。 - 发送端传送一个 2048 字节的数据段，SEQ = 0。

• 接收端缓冲区还剩下 2048 字节，发送确认并指定窗口大小，即发送 ACK = 2048, WIN = 2048。

• 发送端再次传输另一个 2048 字节的数据段，SEQ = 2048。

• 接收端发回确认并宣告窗口大小变为 0，即发送 ACK = 4096, WIN = 0。

  • 此时发送端被阻塞，停止发送数据。
  • 但是紧急数据仍可以发送。
  • 发送端可以发送一个 1 字节的段，以便接收端重新宣告下一个期望字节和窗口大小，称为窗口探测。

低窗口综合征/傻瓜窗口症状：
- 当数据以大块形式被传递给发送端 TCP 实体，但接收端的交互式应用每次仅读取 1 个字节。
于是当接收端缓冲区满时，接收端的应用进程每读取一个字节，发送窗口大小为 1 字节的修正信息。
发送方发送 1 字节数据，窗口很快又满了。

• 解决方案：
  • 禁止接收方发送 1 个字节大小的窗口修正信息，而是等到有了一定数量的可用空间后再通知对方。
  • 发送方不发送太小的数据段。

计时器管理

TCP 维护多个定时器：包括建立、释放连接，确认、重传，滑动窗口三个方面。

连接建立，连接释放： - 连接建立定时器 (Connection Establishment Timer)

当 SYN 数据段发出时，建立连接计时器就开始计时，如果在一定时间内未收到响应，则连接建立失败。

• 保持存活定时器 (Keep-Alive Timer)

  当一个连接长时间闲置时，该定时器会超时，从而使一方去检测另一方是否存在。
  如果它没有得到响应，则种植终止该连接。

• 闲置定时器 (Quiet Timer)

  设置该定时器以防止刚刚断开连接的端口号被立即重新使用。
  即 TIME WAIT 阶段所使用的定时器。

确认、重传： - 重传定时器 (RTO)

当 TCP 实体发送一个段时，它同时启动一个重传计时器。
如果在该计时器超时前该段被确认，则计时器被停止；如果在确认到来前计时器超时，则该段被重传，并且该计时器被重新启动。

使用一个动态算法，根据网络性能的连续测量情况，不断地调整超时间隔。 - RTT（往返时间）：代表到达接收方往返时间的当前最佳估计值。

发送一个段后，如果在计时器超时前确认返回，则 TCP 测量这次确认所花的时间 R。  

第一次测量时：$RTT = R$。

之后每次测量：根据以下**指数加权移动平均**公式更新 RTT 的值。  
$$
RTT = \alpha RTT + (1 - \alpha) R
$$
其中 $\alpha$ 是平滑因子，一般为 $\dfrac{7}{8}$

• RTTVAR（往返时间变化）

  同样的，发送一个段后，如果在计时器超时前确认返回，则 TCP 测量这次确认所花的时间 R。

  第一次测量时：$RTTVAR = R / 2$。

  之后每次测量，根据以下公式更新：
  $$RTTVAR = \beta RTTVAR + (1 - \beta) |RTT - R|$$
  其中 $\beta$ 一般为 $\dfrac{3}{4}$

• RTO（重传超时值）
  $$RTO = RTT + 4 \times RTTVAR$$

Karn 算法：对已经重传的数据段无需修改 RTT 和 RTTVAR，而是在每次传输失败时将超时时间 RTO 加倍，直到该数据段被成功传输。
因为发送端无法区分 ACK 是对哪次发送的 TCP 数据段的确认，所以重发数据段后收到的 ACK 不会更新 RTT 值。

• ACK 延时定时器 (Delayed ACK Timer)

  当 TCP 实体收到数据段时，它启动 ACK 延时定时器。
  在定时器超时前如果有数据段要发送，则在数据段中携带确认信息，并暂停该定时器。
  如果定时器超时时还没有数据段要发送，则单独发送一条确认消息。

滑动窗口： - 持续定时器 (The Persistence Timer)

防止死锁情况：
为了让发送端暂停发送数据，接收端发送一个窗口大小为 0 的确认。之后，接收端又发送了更新了窗口大小的数据段。
如果该数据段丢失，则双方均处于等待。

发送端在收到接收端发来一个窗口大小为 0 的数据段时，启动持续定时器。
如果定时器超时时还没有收到对方修改篡改看大小的数据段，则发送端发送一个 1 字节的探测数据段。
对该探测数据段的响应包含了窗口大小，如果仍为 0，则定时器清零，重新开始计时；否则则可以发送数据。

拥塞控制

每个 TCP 连接需要维护两个窗口： - 接收窗口 (rwnd)：接收端根据目前可用接收缓存大小所许诺的最新窗口值。
在滑动窗口中有所涉及。

• 拥塞窗口 (cwnd)：发送端根据自己估计的网络拥塞程度而设置的窗口值。
  窗口大小时任何时候发送端可以向网络发送的字节数。
  TCP 根据

发送端发送窗口的上限值应该去接收窗口和拥塞窗口中的较小值。

TCP 拥塞控制算法过程： - 慢速启动 - 当一个连接初始化时，将拥塞窗口置为一个最大数据段长度 (MSS)，并设置慢启动阈值 (ssthresh)。

• 发送端的发送窗口不能超过 rwnd 和 cwnd 中的最小值，在这里假定接收端不进行流量控制。

• 发送端收到一个确定，就将拥塞窗口加 1 (MSS)。
  即每经过一个 RTT，拥塞窗口就增加为前一个 RTT 时的两倍，即拥塞窗口从 1 开始按指数规律增长。

• 拥塞控制

  • 采用加法递增乘法递减 (AIMD)

  • 当拥塞窗口增长到 ssthresh 时，TCP 就从慢速启动切换到加法递增。
    即每轮将拥塞窗口加 1，使拥塞窗口按线性规律增大。

  • 如果出现数据包丢失（RTO 超时），就将当前拥塞窗口值减半，作为新的 ssthresh（乘法递减），同时将拥塞串口变为 1。

  • TCP 重新开始慢速启动过程。

• 快速重传

  • 发送端只要连续收到三个重复的 ACK 即可断定有数据包丢失。
    因为丢失数据包后续的数据包触发接收端返回的确认携带相同的确认号（期望收到的数据包没变）。

  • 上述情况下立即重传丢失的数据包而不必等待 RTO 超时。
    同时像超时情况下一样处理拥塞窗口（乘法递减）。

• 快速恢复 (Reno 算法，是 TCP 推荐算法，不是必须)

  • 当发送端收到连续三个重复 ACK 时，重新设置 ssthresh 为当前拥塞窗口的一半。
    但拥塞窗口不是设置为 1，而是设置成 ssthresh + 3。

  • 如果收到了重复的 ACK（说明又有丢失数据包之后的数据包到达了接收端，网络里的数据包减少了一个），则每收到一个重复 ACK，就将拥塞窗口加 1。

  • 若收到了重传数据包的 ACK（新的 ACK），则将拥塞窗口设置到 ssthresh，再次执行 AIMD。

TCP 的传输速率： - 设 TCP 的发送窗口为 w，往返时间为 RTT，则 TCP 瞬时最大发送速率为 $\dfrac{w}{RTT}$。 - 由于 w 是变化的，设丢包或收到三个重复 ACK 时的窗口为 W 且 W 不变，则 w 在 W/2 到 W 之间变化。
忽略慢速启动阶段，则一条连接的平均吞吐量为 $0.75 \times \dfrac{W}{RTT}$。

第4章 MAC 子层

• 传统 LAN 基本概念
• 多路访问协议
  • 信道分配
    • 静态信道分配
    • 动态信道分配
  • ALOHA 协议
    • 纯 ALOHA
    • 分槽 ALOHA
  • CSMA 协议
    • 1-坚持式 CSMA
    • 非坚持式 CSMA
    • p-坚持式 CSMA
    • CSMA/CD
    • CSMA/CA
    • 二进制指数后退
  • 冲突避免多路访问 (MACA)
• 以太网 (IEEE 802.3)
  • 经典以太网
    • 帧格式
    • MAC 子层协议
  • 交换式以太网
    • 快速以太网 (Fast Ethernet)
    • 千兆以太网 (Gigabit Ethernet)
• 无线局域网 (802.11)
  • 体系结构
  • MAC 子层协议
    • 带冲突避免的 CSMA
    • 物理侦听/虚拟侦听
    • 可选的 RTS/CTS 机制
    • 时间间隔
  • 帧格式
• 局域网互联设备
  • 网桥
    • 学习网桥
    • 生成树网桥
    • 存在的问题
  • 交换机
  • 不同设备对比

传统 LAN 基本概念

局域网 (LAN)：在一个小区域范围内对各种数据通信设备提供了互连的信息网。

决定局域网特性的主要技术： - 传输媒体： 传输数据 - 拓扑结构：连接各种设备 - 媒体访问控制方法：共享资源

局域网的数据链路层： - 逻辑链路控制子层 (LLC) - 媒体访问控制子层 (MAC)：用来确定多路访问信道下一个使用者的协议

LAN 的传输媒体： - 双绞线 - 同轴电缆 - 光纤 - 无线电波 - 红外

LAN 的拓扑结构： - 星型 - 环型 - 总线型 - 树型

多路访问协议

信道分配

信道分配问题：如何在竞争用户之间分配单个广播信道。

静态信道分配

采用多路复用技术，将信道容量拆开分给多个用户使用。
如传统的 FDM 或 TDM，对于 N 个用户，将带宽或时间分成 N 份，每个用户静态地占用一个。

缺点：不能有效地处理突发数据，有些用户停止通信时带宽或时间被浪费。

动态信道分配

异步时分多路复用。分为以下两种： - 随机访问：争用。只要有数据就直接发送，发生冲突后再采取措施解决冲突。
适用于负载轻的网络，负载重时效率低

• 控制访问：发送站点先获得发送的权利，再发送数据。
  不会发生冲突，在负载重的网络中可获得很高的信道利用率。
  主要有轮询和预约两种方式。

动态信道分配的5个关键假设： - 流量独立
由 N 个独立的站组成，每个站都有一个程序或用户产生要传输的帧。

• 单信道
  所有用户都共享同一个信道，在该信道上发送/接收数据。

• 冲突可观察
  冲突：如果多个用户同时发送数据，多路信号在时间上叠加使接收端无法正常解码。
  所有站都能够检测到冲突事件的发生，冲突的帧必须在以后再次被发送。

• 时间连续或分槽
  时间连续：任何时刻都可以开始传输帧。
  时间分槽：将时间分为离散的间隔（称为时间槽），帧的传输只能从某个时间槽的起始点开始。

• 载波侦听或不听
  载波侦听：发送前先侦听信道，可以知道该信道当前是否正被使用。

ALOHA 协议

纯 ALOHA

当用户有数据需要发送时就传输。

每个站在给中央计算机发送帧之后，该计算机把该帧重新广播给所有站。
发送站侦听来自集线器的广播，以此确定它的帧是否发送成功。

如果帧被损坏了，则发送方等待一段随机时间后再次发送该帧。

分槽 ALOHA

将信道时间分为离散的时间槽，每个时间槽可以用来发送一个帧。
一个站点有数据发送时，必须等到下个时间槽的开始才可以发送。

与纯 ALOHA 相比，信道利用率提高一倍。

CSMA 协议

载波侦听多路访问 (CSMA) 协议：站监听信道，根据信道的状态来采取相应的动作，只有发现信道空闲时才能发送数据。

1-坚持式 CSMA

当一个站点要发送数据时，先监听信道，若信道忙则坚持监听；一旦发现信道空闲，立即发送数据（发送数据概率为 1）。
若发生冲突，等待一随机场时间，再重新开始监听信道。

两种发生冲突可能： - 信号传输延迟造成冲突 - 多个站点在监听到信道空闲时同时发送

该协议的性能高于 ALOHA 协议。

非坚持式 CSMA

当一个站点要发送数据时，先监听信道，若信道忙，随机等待一段时间后再开始监听信道（非坚持）；一旦发现信道空闲，立即发送数据。

该协议的信道利用率高于 1-坚持式 CSMA 协议，但网络的延迟增大。

p-坚持式 CSMA

适用于分时间槽的信道。

当一个站点要发送数据时，先监听信道，若信道忙，则等到下个时间槽再监听信道；若信道空闲，则按照概率 p 发送数据，而以概率 q=1-p 将此次发送推迟到下一个时间槽。若下一个时间槽信道也是空闲的，则它还是以概率 p 发送数据，或者以概率 q 再次推迟发送；重复该过程直到帧被发送出去。

与前两种 CSMA 协议相比： - 概率 p：降低 1-坚持式协议中多个站点同时发送而造成冲突的概率。 - 坚持监听：克服非坚持式协议中造成的时间延迟。

p 的选择直接关系到协议的性能。

CSMA/CD

带冲突检测的 CSMA (CSMA/CD)
发送过程中仍然监听信道，通过检测回复信号的能量或脉冲宽度并将其与发送的信号作比较，可以判断是否发生冲突。
一旦发生冲突，立即取消发送，等待一随机时间后再尝试发送。

检测冲突的最小时间是将信号从一个站传播到另一个站所需要的时间。

CSMA/CA

带避免冲突的 CSMA，被 WLAN 采用。

• 通过侦听确定在很短的一个时间内（这段时间称为 DIFS）没有信号。
• 倒计数空闲时间槽，当有帧在发送时暂停该计数器。
• 当计数器递减到0时，该站发送自己的帧。
• 如果帧发送成功，目标站立即发送一个短确认。
• 如果该站没有收到确认，则说明传输过程中发生了错误，采用二进制指数后退算法重新发送。

二进制指数后退

如果发生冲突，等待一段随机时间后再重试。
一般地，在第 i 次冲突之后，从 $0$ ~ $2^i-1$ 之间随机选择一个数，然后等待这么多个时间槽。
在达到10次冲突之后，随机数的选择区间被固定在最大值1023，不再增加。
在16次冲突之后，控制器放弃努力，并给计算机返回一个失败报告，进一步的恢复工作由高层协议完成。

冲突避免多路访问 (MACA)

• A 向 B 发送一个 RTS (Request To Send) 短帧，包含了随后要发送的数据帧长度。
• B 向 A 回复一个 CTS (Clear To Send) 短帧，包含了从 RTS 中复制的数据帧长度。
• A 收到 CTS 后开始传输。
• 如果一个站侦听到了 RTS，则它保持足够长时间的沉默使 A 能在无冲突的情况下收到 CTS。
  该站如果只侦听到了 RTS 没有侦听到 CTS，则在数据帧传送过程中可以自由发送信息。
• 如果一个站侦听到了 CTS，则它依据 CTS 中数据帧的长度，在数据传输过程中一直保持沉默。

以太网 (IEEE 802.3)

经典以太网：使用上述技术解决多路访问问题。
以太网的原始形式，运行速度从 3~10 Mbps 不等。

交换式以太网：使用交换机连接不同的计算机。
可以运行在 100、1000 和 10000 Mbps 的高速率，分别以快速以太网、千兆以太网和万兆以太网的形式呈现。

经典以太网

帧格式

• 前导码 (Preamble)：8个字节，每个字节包含比特模式 10101010。IEEE 802.3 最后一个字节（帧起始定界符 SOF）的最后2位为11。
  比特模式是由曼彻斯特编码产生的 10MHz 方波，每个波 6.4 微妙，以便接收方的时钟与发送方同步。

• 目标地址：6个字节，MAC 地址，第一位是0表示是普通地址；如果是1，则表示组地址，该组中的所有站都要接收；全1的特殊地址用作广播，网络中的所有地址都要接收。

• 源地址：6个字节，MAC 地址，标识帧的发送方，具有全球唯一性。
  地址字段的前3个字节用作该站所在的组织唯一标识符 (OUI)，由 IEEE 统一分配，指明了网络设备制造商；后3个字节由制造商负责分配。

• 类型/长度 (Type/Length)：2个字节。以太网使用类型字段，指定了该把帧送给哪个进程处理。IEEE 802.3 使用长度字段，接收方通过数据内包含的另一个逻辑链路控制 (LLC) 协议头来确定如何处理入境帧。
  任何值小于或等于 0x600 可解释为长度字段，任何大于 0x600 可解释为类型字段。

• 数据 (Data)：最多可包含 1500 字节。

• 填充 (Pad)：最多 46 字节。以太网要求有效帧必须至少 64 字节长，从目标地址算起直到校验和，包括这两个字段本身在内。如果帧的数据部分小于 46 字节，则使用填充字段来填充该帧，使其达到最小长度要求。

  限制最小帧长的原因：避免当一个短帧还没有到达电缆远端的发送方，该帧的传送就已经结束；这种情况下，当在电缆的远端发生冲突时，发送方的传送在突发噪声到达前就完成传送，发送方误以为刚才一帧已成功发送。

• 校验和：4个字节，采用 32位CRC。

MAC 子层协议

采用 1-坚持 CSMA/CD 算法，发生冲突时采用 二进制指数后退算法。

1-坚持式 CSMA，CSMA/CD，二进制指数后退

交换式以太网

当交换机端口接收到来自某个站的以太网帧，它检查该帧的以太网地址，确定该帧前往的目的地端口。

• 在集线器中，所有站位于同一个冲突域（不同站点同时发送数据可能产生碰撞的最大网段），必须使用 CSMA/CD 算法。
• 在交换机中，每个端口有独立的冲突域。
  • 对于全双工电缆，冲突不可能发生。
  • 对于半双工电缆，站和端口以通常的 CSMA/CD 方式竞争传输。

快速以太网 (Fast Ethernet)

IEEE 802.3u 工作组规范 (1995, 6)。

特点： - 采用 CSMA/CD 媒体访问控制方式和 802.3 帧格式； - 100 BASE-TX 采用两对5类双绞线； - 100 BASE-T4 采用四对3类双绞线； - 网络最大长度 250m (10 Mbps 的经典以太网是 2500m)。

千兆以太网 (Gigabit Ethernet)

IEEE 802.3z (1998) 和 802.3ab 工作组规范。

特性： - 载波扩充：让硬件在普通的帧后面增加一些填充位，将帧的长度扩充到 512 字节，使网络最大距离延长到 200m。 - 帧突发：允许发送方将多个待发送帧级联在一起，一次传输出去。最大突发长度为 8192 字节。如果级联起来的整个突发仍然小于 512 个字节，则硬件会再次对它进行填充。 - 全双工。

无线局域网 (802.11)

WLAN：无线局域网，是计算机网络和无线通信技术相结合的产物，是有线网络的无线化延伸。
Wi-Fi：是一个创建于 IEEE 802.11 标准上的无线局域网技术，可等同于 802.11 的同义词。
无线局域网的主要标准是 802.11。

体系结构

接入点 (AP)：转发该 WLAN 上的所有帧，具备无线至有线的桥接功能。
工作站 (Station)：具备 WLAN 接口，能接入 WLAN 的主机。
分布式系统 (DS)：一种有线网络，是 802.11 的逻辑组件，负责连接多个 AP，或将 AP连接至骨干网（如目前已知的以太网）。

基本服务集 (BSS) - 独立基本服务集 (IBSS, independent BSS)：工作站之间相互可以直接通信（不需要通过 AP 转发）。 - 基础结构型基本服务集 (infrastructure BSS)：工作站需先与接入点建立关联，接入点负责转发工作站之间的通信。 - 每个 BSS 都有一个6字节的识别符 BSSID，相当于 AP 的 MAC 地址。

扩展服务集 (ESS)：将几个 BSS 连接为 ESS。

MAC 子层协议

带有物理侦听和虚拟侦听的 CSMA/CA 是 802.11 协议的核心。

802.11 允许把帧拆分为更小的单元段 (fragment)，每个段有自己的校验和。

带冲突避免的 CSMA

802.11 支持两种操作模式 - 点协调功能 (PCF)：由 AP 周期性地（每秒10~100次）广播一个信标帧，邀请站点申请服务，集中控制。

• 分布式协调功能 (DCF)：分布式控制，采用带有冲突避免的 CSMA (CSMA/CA)。

• DCF 是必须的，PCF 是可选的。

与以太网相比，CSMA/CA 有两个主要区别： - 早期的后退有助于避免冲突； - 利用确认来推断是否发生冲突，因为冲突无法被检测出来。

物理侦听/虚拟侦听

由于 WLAN 中各个站点发出的信号范围有限，使用 CSMA 时存在两个问题： - 隐藏终端问题：由于竞争者距离太远而导致站无法检测到潜在的竞争者，误以为可以发送数据。 - 暴露终端问题：站点侦听到信道上有帧在传送，错误地认为自己不能发送数据。

为了解决上述问题，802.11 定义信道侦听包括物理侦听和虚拟侦听两部分。 - 物理侦听：检测信道是否存在有效信号。 - 虚拟侦听：让源站将它要占用信道的时间通知给所有其他站，使其他站不需要侦听就能知道信道何时可能转为空闲。

网络分配向量 (NAV)：每个帧携带一个 NAV 字段，说明这个帧所属的一系列数据将传输多长时间。
当一个站检测到正在信道中传输的 MAC 帧首部的 NAV 字段时，就调整自己的 NAV。

可选的 RTS/CTS 机制

使用 NAV 来防止隐藏终端在同一时间发送，与 MACA 类似。
不同之处： - A 发送数据帧时启动一个 ACK 计时器； - 当正确的数据帧到达后，B 用一个 ACK 帧回复 A，完成此次交流； - 如果 A 的 ACK 计时器超时前，ACK 没有返回，则可视为发生了一个冲突，经过一次后退整个协议重新开始运行； - 听到 RTS/CTS 的站会更新自己的 NAV 记录表示信道正忙。

RTS/CTS 的引入带来了延时和信道资源的消耗，因此该机制只用于预约长数据帧的信道。实际中，每个无线站点可设置一个 RTS 门限，仅当数据长度超过门限时才使用该机制。

时间间隔

一帧发送出去后，需要保持一段特定时间的空闲以便检查信道不在被用，然后任何站才可以发送帧。

• 短帧间间隔 (SIFS)：最短的间隔；允许一次对话的各方具有优先抓住信道的机会，可以发送控制帧（如 ACK、RTS、CTS）或下一个段。

• DCF 帧间隔 (DIFS)：常规的数据帧之间的间隔；任何站都可以在介质空闲 DIFS 后尝试抓取信道发送一个新帧，采用通常的竞争规则。

• 仲裁帧间空间 (AIFS)：有两个不同的优先级。

  • AIFS1：小于 DIFS 但长于 SIFS；被 AP 用来把语音或其他高优先级流量移到行头。
  • AIFS4：长于 DIFS；用来发送可以延迟到常规流量之后发送的背景流量。
  • 完善的服务质量机制定义了四种不同的优先级别，分别具有不同的后退参数和不同的空闲参数。

• 扩展帧间间隔 (EIFS)：最长；仅用于一个站刚刚收到坏帧或未知帧后报告问题。

时间间隔长度与媒介有关，速率高的物理层会使用较短的间隔；同样，不同的物理层帧间间隔也有所不同。

帧格式

• 帧控制 (Frame Control):2 个字节，包含 11 个子字段。

  • 协议版本 (Protocol Version)：2 比特，00。
  • 类型 (Type)：2 比特，数据帧、控制帧或管理帧。
  • 子类型 (Subtype)：4 比特，比如 RTS 或 CTS。
  • To DS：1 比特，表明发送到分布式系统。
  • From DS：1 比特，表明来自分布式系统。
  • 更多段 (More fragment)：1比特，表明后面还有更多的段。
  • 重传 (Retry)：1比特，表明这是以前发送的某一帧的重传。
  • 电源管理 (Power management)：1 比特，指明发送方进入节能模式。
  • 更多数据 (More data)：1 比特，表明发送方还有更多的帧需要发送给接收方。
  • 受保护的 (Protected Frame)：1 比特，表明该帧的帧体已经被加密。
  • 顺序 (Order)：1 比特，告诉接收方高层希望严格按照顺序来处理帧序列。

• 持续时间 (Duration)：2个字节。
  通告本帧和其确认帧将会占用信道多长时间，按微妙计时。
  该字段会出现在所有帧中，包括控制帧，其他站用该字段来管理各自的 NAV 机制。

• 地址：共有三个地址字段，每个均有 6 个字节。

  • 地址1：接收方地址。
  • 地址2：发送方地址。
  • 地址3：当帧在一个客户端和网络中的另一点传输时，AP 是一个中继点，地址3指明了这个远程端点。
  • 当 To DS 和 From DS 都置1时，在序号字段后有 6 个字节的地址4。

• 序号 (Sequence)：2 个字节。
  帧的编号，用于重组帧片段以及丢弃重复帧。
  有 4 位段序号和 12 位帧序号。相当于已传帧的计数器，计数器从0计数，每传输一帧序号+1，取 4096 的模数。

• 数据 (Data)：最多可有 2312 个字节。
  有效荷载中前面部分字节的格式称为逻辑链路控制 (LLC)，标识有效荷载应该递交给哪个高层协议处理（比如 IP）。

• 帧校验序列 (Frame check sequence)：4 个字节。
  32 位 CRC。

RTS 共20字节：帧控制、持续时间、目的地址、源地址和检错字段。
CTS 和 ACK共14字节：帧控制、数据长度、目的地址和检错字段。

局域网互联设备

网桥

• 用于连接局域网的互连设备。
• 工作在数据链路层，通过检查数据链路层地址（MAC 地址）来转发帧，必要时进行帧格式转换。
• 能隔离以太网中的碰撞域，但不能隔离广播域。
• 丢弃出错帧。
• 包括透明网桥和源路由选择网桥，以下两种都是透明网桥。

学习网桥

为每个网桥配备一个大的哈希表，该表列出每个可能的目的地以及它们隶属的输出端口。

当网桥第一次接入网络时，所有哈希表都是空的，采用泛洪算法：
对于每个发向未知目标地址的入境帧，网桥将它输出到所有端口，除了它来的输入端口。

采用后向学习法：
通过检查每个端口发送的帧的源地址，网桥可以知道通过该端口可以访问到哪些机器，于是在哈希表上构造相应的一对地址和端口。

为了处理动态的拓扑结构：
构造出哈希表后，帧的到达时间也被记录在相应的表项中。
当一帧到达时，如果它的源地址已经在表中，那么对应表项中的时间值被更新为当前时间。
网桥中存在一个进程定期扫描哈希表，将时间值在几分钟之前的表项都清除掉。

对到达网桥的入境帧，整个转发过程如下：
- 如果去往目的地址的端口与源端口相同，则丢弃该帧； - 如果去往目的地址的端口与源端口不同，则转发该帧到目标端口； - 如果目标端口未知，则使用泛洪算法，将该帧转发到所有端口，除了它入境的哪一个。

网桥可看作链路层设备，一个具有 k 个端口的网桥将有 k 个 MAC 和物理层实例。

生成树网桥

为了提高可靠性，在网桥之间使用冗余链路，如在一对网桥之间并行设置两条链路。

为了解决拓扑环路问题：
让网桥之间相互通信，用一棵可以到达每个网桥的生成树覆盖实际的拓扑结构。
- 选择具有最低标识符的网桥为生成树的根。 - 构造从根到每个网桥的最短路径树，碰到平局时，选择一条经过更低标识符的网桥的路径。 - 网桥在被指消息中包括与根的距离，每个网桥记住它找到的到根的最短路径。 - 网桥关闭不属于最短路径一部分的端口。

存在的问题

在连接不同类型的局域网（如 802.3 和 802.11）时，网桥的转发存在以下主要问题。

• 帧格式不同。
  需要重新组帧，某些域（如 802.11 帧的持续时间）需要丢弃或产生，还需要重新生成校验和。

• 数据速率不同，802.11 速率较低。
  网桥需要用缓冲区存储来不及传输的帧。

• 最大帧的长度不同。
  802 标准本身不提供把长帧分片的功能，对于太长的帧只能丢弃。

• 安全性问题。
  802.11 支持加密，802.3 不支持。

• 服务质量问题。
  802.11 采用 PCF 可以支持 QoS，802.3 不支持。

交换机

交换机源自于多端口网桥，采用存储-转发方式在各端口之间进行数据帧的交换。

交换机检测每个到达数据帧的帧头，根据数据帧的目的地址查找输出端口。
如果地址查找表中没有该表项，交换机就向所有端口（除了接收端口）转发。
地址查找表是通过帧的源地址与到达端口的对应关系建立的。

工作在数据链路层，能隔离碰撞域。

交换式局域网：采用星型拓扑结构，用交换机连接主机。

不同设备对比

帧（由数据链路层构造）包含： - 帧头 - 数据包头 - TCP 头 - 用户数据 - CRC

数据包（由网络层构造）包含其中的： - 数据包头 - TCP 头 - 用户数据

第5章 网络层

• 向传输层提供的服务
• 无连接服务/面向连接服务的实现
  • 数据报网络
  • 虚电路网络
  • 二者对比
• 路由算法
  • 优化原则
  • 最短路径算法
    • Dijkstra
    • Bellman Ford
  • 泛洪算法
  • 距离矢量 (Distance Vector) 路由算法
    • 存在问腿
  • 链路状态 (Link State) 路由算法
    • 与距离矢量算法比较
  • 层次路由 (Hierarchical Routing)
• 拥塞控制算法
  • 开环控制
    • 漏桶算法
    • 令牌桶算法
  • 闭环控制
    • 虚电路中的拥塞控制
    • 数据报中的拥塞控制
• 服务质量
• 网络互连
  • 网络如何不同
  • 网络如何连接
  • 互联网路由
  • 数据包分段
    • 透明分段
    • 不透明分段
    • 路径 MTU 发现
• Internet 的网络层
  • IPv4 协议
  • IPv4 地址
    • 前缀/子网
    • IP 地址和 MAC 地址
  • IP 寻址
    • 路由表与转发表
    • 无类域间路由 (CIDR)
    • 分类和特殊寻址
    • NAT
  • IPv6 协议
    • 扩展头
  • IPv6 地址
    • 分类
  • Internet 控制协议
    • ICMP
    • ARP
    • DHCP
  • Internet 路由协议
    • RIP
    • OSPF
    • BGP
    • 路由协议分类与协议栈
  • Internet 组播
    • 组播路由协议

向传输层提供的服务

网路层的必要性：
- 相距较远的局域网之间的互联互通需要有结构化的统一的地址编排，而 MAC 地址是硬件地址，与位置无关，无法用来路由。 - 二层交换机不隔离广播域，网络规模较大时易形成广播风暴。

网络层设计目标： - 向上提供的服务应该独立于路由器技术。 - 应该向传输层屏蔽路由器的数量、类型和拓扑关系。 - 传输层可用的网络地址应该有一个统一的编址方案，甚至可以跨越 LAN 和 WAN。

争论： - 网络层提供面向连接的服务还是无连接的服务。

无连接服务/面向连接服务的实现

OSI 的网络层提供两种服务 - 面向连接：虚电路 - 无连接：数据报

数据报网络

所有的数据包都被独立地注入到网络中，并且每个数据包独立路由，不需要提前建立任何设置。

特点： - 如果分组的寻路是独立的，可以合理利用网路资源。 - 如果途中一个节点或一条链路发生故障，能给分组重选路由。 - 分组头需要包含地址字段，会增加开销。 - 各分组途经的路径可能不同，又肯出现先发后到现象。 - 分组必须有生存时间限制，当生存期满时，分组则被抛弃；避免在网络内死转。

虚电路网络

在发送数据包之前，必须首先建立起一条从源路由器到目标路由器之间的路径。
每个数据包包含一个标识符，指明了它属于哪一条虚电路。

特点： - 一条物理链路可以对应多条逻辑信道。 - 一条虚电路由各物理链路上的逻辑信道级联而成，占用了节点上的一条逻辑信道实际上就是占用了该节点上缓存器内的一个存储空间。 - 分组考逻辑信道号 (LCN) 选择路由；因 LCN 只有局部意义，所以减少了分组头标的开销和处理的复杂度。 - 能有效防止拥塞。

二者对比

路由算法

网络层的主要功能是根据分组目的地址选择路径。

路由算法是网络层软件的一部分，负责确定一个入境数据包应该被发送到哪一条输出线路上。 - 对数据报，路由器针对每一个到达的数据包重新选择路径。 - 对虚电路，只有当建立一条新的虚电路时才需要做路由决策。

路由算法可以分成两大类： - 非自适应算法： - 不会根据当前测量或者估计的流量和拓扑结构，来调整它们的路由决策。 - 路由表固定，也称为静态路由。 - 简便、可靠、易行，适用于负荷稳定、拓扑结构变化不大的网络。 - 自适应算法： - 根据拓扑结构的变化、流量的变化情况改变路由决策。 - 路由表定时刷新，也称为动态路由。 - 算法复杂，会增加网络负担，但能根据网络状态动态调整路由表，改善网络的性能。

路由器上可以同时运行多个路由协议，当有到达同一个目的地址的多条路由时，可以根据优先级的大小，选择其中一个优先级数值最小的作为最优路由。

优化原则

最优化原则：如果路由器 J 在从路由器 I 到路由器 K 的最优路径上，那么从 J 到 K 的最优路径也必定遵循同样的路由。

汇集树：从所有的源到一个指定目标的最优路径的集合构成了一棵以目标节点为根的树。

所有路由算法的目标是为所有路由器找到这样的汇集树，并根据汇集树来转发数据包。

最短路径算法

Dijkstra

在全双工链路连接的网络上，每条链路的每个方向上都有一个与之相关的权值。两个节点之间一条路由的代价是它所经过的链路权值之和。这两个节点间的最佳路由为其所有可能路径中具有最小代价的那条路径。

标示路径长短的度量可以有：跳数、物理距离、带宽、平均流量、通信成本、平均延迟等。

eg. 整个图的状态（空格表示没有直接连接）： | | A | B | C | D | E | F | |:-:|:-:|:-:|:-:|:-:|:-:|:-:| | A | - | 4 | | | 5 | | | B | 4 | - | 2 | | | 6 | | C | | 2 | - | 3 | 1 | | | D | | | 3 | - | | 7 | | E | 5 | | 1 | | - | 8 | | F | | 6 | | 7 | 8 | - |

求解从 A 出发到其他节点的最短路径。

• 初始化，除源节点 (A) 外，所有节点均为临时节点（表示未找到到该点的最短路径）。
  除了与自身相邻的节点外，源节点到其余节点的距离都为无穷（实际编程时用一个很大的数表示）。

  目的节点	性质	路径	距离
  B	临时	B	4
  C	临时		$\infty$
  D	临时		$\infty$
  E	临时	E	5
  F	临时		$\infty$

• 从所有临时节点中找到距离最短的 (B) ，将其变为永久节点（表示已经找到到该点的最短路径）。
  从该节点 (B) 出发，寻找源节点到其余临时节点是否有更近的路径。

  目的节点	性质	路径	距离
  B	永久	B	4
  C	临时	B + C	6
  D	临时		$\infty$
  E	临时	E	5
  F	临时	B + F	10

• 重复上述过程，直到所有节点都成为永久节点。

  目的节点	性质	路径	距离
  B	永久	B	4
  C	临时	B + C	6
  D	临时		$\infty$
  E	永久	E	5
  F	临时	B + F	10

  目的节点	性质	路径	距离
  B	永久	B	4
  C	永久	B + C	6
  D	临时	B + C + D	9
  E	永久	E	5
  F	临时	B + F	10

  目的节点	性质	路径	距离
  B	永久	B	4
  C	永久	B + C	6
  D	永久	B + C + D	9
  E	永久	E	5
  F	临时	B + F	10

  目的节点	性质	路径	距离
  B	永久	B	4
  C	永久	B + C	6
  D	永久	B + C + D	9
  E	永久	E	5
  F	永久	B + F	10

Bellman Ford

eg. 整个图的状态（空格表示没有直接连接）： | | A | B | C | D | E | F | |:-:|:-:|:-:|:-:|:-:|:-:|:-:| | A | - | 4 | | | 5 | | | B | 4 | - | 2 | | | 6 | | C | | 2 | - | 3 | 1 | | | D | | | 3 | - | | 7 | | E | 5 | | 1 | | - | 8 | | F | | 6 | | 7 | 8 | - |

• 初始状态路由表中每两个路由器间的距离都为无穷。

• 第一次交换可以得到相邻节点的信息（距离和转发节点）： | | A | B | C | D | E | F | |:-:| :-: | :-: | :-: | :-: | :-: | :-: | | A | - | 4/B | | | 5/E | | | B | 4/A | - | 2/C | | | 6/F | | C | | 2/B | - | 3/D | 1/E | | | D | | | 3/C | - | | 7/F | | E | 5/A | | 1/C | | - | 8/F | | F | | 6/B | | 7/D | 8/E | - |

  其中列表示源节点，行表示目标节点，表格中的值为 距离/出口节点。
  每一行为对应路由器中路由表存储的内容。

• 第二次交换更新相邻节点当前具有的信息，从相邻节点处获得到达新节点的路径，并比较几条路径选出最短的：
  | | A | B | C | D | E | F | |:-:| :-: | :-: | :-: | :-: | :-: | :-: | | A | - | 4/B | 6/B | | 5/E | 10/B | | B | 4/A | - | 2/C | 5/C | 3/C | 6/F | | C | 6/B | 2/B | - | 3/D | 1/E | 8/B | | D | | 5/C | 3/C | - | 4/C | 7/F | | E | 5/A | 3/C | 1/C | 4/C | - | 8/F | | F | 10/B | 6/B | 8/B | 7/D | 8/E | - |

• 第三次交换，同上：
  | | A | B | C | D | E | F | |:-:| :-: | :-: | :-: | :-: | :-: | :-: | | A | - | 4/B | 6/B | 9/B | 5/E | 10/B | | B | 4/A | - | 2/C | 5/C | 3/C | 6/F | | C | 6/B | 2/B | - | 3/D | 1/E | 8/B | | D | 9/C | 5/C | 3/C | - | 4/C | 7/F | | E | 5/A | 3/C | 1/C | 4/C | - | 8/F | | F | 10/B | 6/B | 8/B | 7/D | 8/E | - |

  至此路由表更新完成。

泛洪算法

将每一个数据包发送到除了该数据包到达的那条线路以外的每条出境线路。

为了抑制数据包泛滥，可以： - 在每个数据包的头中设置一个跳计数器，每经过一跳该计数器减一，当计数器到达 0 时就丢弃该数据包。
理想情况下，跳计数器的初始值应该等于从源端到接收方之间路径的长度。
如果发送方不知道该路径有多长，可以将计数器的初始值设置为最坏情况下的长度，即网络的直径。

• 每个源路由器在接收来自主机的数据包时填上一个序号，每个路由器为每个源路由器准备一张表，记录已经观察到的来自源路由器的序号。如果入境数据包在该表中，它就不能再被泛洪到其他路由器。
  每个表使用一个计数器 k 作为参考，它表示直到 k 的所有序号都已经观察到了。

距离矢量 (Distance Vector) 路由算法

使用 Bellman Ford 算法。

• 每个路由器维护一张路由表，它以网络每个路由器为索引，并且每个路由器对应一个表项，包含：
  • 到达该目标路由j器的首选出境线路；
  • 到达该目标路由器的距离估计值
• 每个路由节点定期地向它的相邻路由节点交换路由表。
• 每个节点根据收到的相邻节点的路由信息更新自己的路由表，最终发现到每个目标的最佳估计值。

存在问腿

收敛：整个网络最佳路径寻找的过程。

对于距离矢量路由算法，它总是能收敛到正确的答案，但速度可能非常慢。它对好消息的反应非常迅速，而对于坏消息的反应异常迟缓。

无穷计算问题：当路由器 A 停机或 A、B 之间的链路断开时，路由器 B 认为可以从 C 到达 A，但实际上 C 的路线是经过 B 的，无法到达 A。逐渐地，所有的路由器都会趋向无穷大，但是所需的交换次数依赖于代表无穷大的数值。

解决方案：水平分割算法。
防止路由器向邻居返回一个从该邻居获得的最佳路径。

链路状态 (Link State) 路由算法

也叫最短路径优先 (SPF) 算法。

• 发现邻居节点，了解其网络地址。

  当一个路由器启动时，在每一条点到点线路上发送一个特殊的 HELLO 数据包。线路另一端的路由器返回一个应答说明自己是谁。
  对于广播 LAN，可以视作一个新的人造节点，LAN 上的一个指定路由器被选中替代该节点运行路由协议。

• 设置到每个邻居节点的距离或成本度量值。

  常用的选择是使成本与链路带宽成反比。
  如果网络在地理上分散，链路的延迟可作为成本的组成部分（发送 ECHO 数据包获得延迟估算值）。

• 构造一个包含所有刚刚获知的链路信息包。

  该数据包的内容首先是发送方的标识符，接着使一个序号和年龄，以及一个邻居列表。对于每个邻居，同时要给出到这个邻居的延迟。
  可以周期性地创建数据包，也可以每当发生某些重要的使其时才创建数据包。

• 将这个包发送给所有其他的路由器，并接收来自所有其他路由器的信息包。

  基本思路是使用泛洪算法将链路状态数据包分发给所有路由器。
  每个数据包包含一个序号，序号随着每一个新数据包发出而逐一递增。
  序号之后包含一个年龄字段，每秒中将年龄减一，为 0 时丢弃该数据包。

• 计算出到每个其他路由器的最短路径。

  在路由器本地运行 Dijkstra 算法。

与距离矢量算法比较

• 需要更多的内存和计算，在大型网络中运行存在问题。
• 没有慢收敛问题。
• 可扩展性好，可靠。

层次路由 (Hierarchical Routing)

路由表项大小与网络规模成正比，当网络规模变大时，路由表也变大，消耗更多的内存、带宽、查找时间。

采用层次化路由解决问题： - 将网络分区域，区域内的路由器只负责本区域内的分组转发，目的地址不在本区域内的分组都发给指定的区域路由器（边界路由器）去处理。 - 路由信息的交换旨在域内进行，路由器内部需存储的路由表项大大减少。 - 对于大型网络，可以分成多层次结构，每一层次的边界路由器相互之间交流路由信息。

缺点：选择的路由可能不是最佳的，增加了路径长度。

对于一个包含 N 个路由器的网络，最优的层数是 lnN，每个路由器所需的路由表项是 elnN 个

拥塞控制算法

拥塞：当大量分组进入通信子网，超出了网络的处理能力时，就会引起网络局部或整体性能下降。 - 路由器的队列溢出，分组丢失。 - 后果：使许多分组重传；导致更多的业务量，直至崩溃。 - 原因：路由器的处理速度、存储空间、带宽不匹配，网络负载的不平衡。

拥塞控制： - 网络负载的不均衡。 - 是全局问题，涉及的节点包括主机、路由器。 - 由网络层和传输层共同承担。

流量控制： - 接收端或所在网络的接受速度小于发送端的发送速度。 - 是局部问题，只涉及收发两端。

指示网络拥塞的参数： - 分组丢失率 - 平均队列长度 - 分组重传率 - 评价分组延时

开环控制

基于良好的设计，进行业务量整形。

漏桶算法

无论流入漏桶的水的速率多大，只要漏桶中还有水，那么水流出桶的速率为恒定速率 R；如果桶内没有水，则流出桶的速率降为 0。
一旦桶内的水达到桶的容量 B，任何额外进入桶的水都会沿着桶侧分流，最终流失。

每个主机在连接到网络的接口中包含一个漏桶。为了向网络发送数据包，漏桶必须由空余。
如果桶满时有数据包到达，那么该数据包必须排入队列等待漏桶空出来时再接纳，或者被丢弃。

令牌桶算法

水龙头向水桶中灌水。水龙头速率为 R，水桶容量为 B。
为了发送一个数据包，必须能够从桶内掏出水或令牌。桶内只能积累固定数量的令牌，即 B。
如果桶是空的，必须等待更多的令牌到达才能发送另一个数据包。

最大突发长度：清空令牌桶所需时间。
假设突发长度为 S 秒，最大输出率为 M B/s，令牌桶的容量为 B 字节，令牌到达率为 R B/s。
则 $B + RS = MS$。

闭环控制

基于反馈概念。

• 检测到拥塞时，就发一个分组给源端，或向所有主机广播。
• 在每个分组头中保留一个位或域，当拥塞超过一定值时，路由器就在该位或域上填上拥塞信息通知网络节点。
• 由主机或路由器发送询问分组查询拥塞情况。

虚电路中的拥塞控制

采用准入控制 (Admission Control) 的三种策略： - 一旦出现拥塞的信号，就不再创建任何虚电路，直至拥塞解除。 - 允许建立新的虚电路，但要仔细选择路由，以便所有新的虚电路绕过拥塞的区域。 - 在虚电路建立时，子网与主机对所需服务质量进行协商。
若不能满足主机最低要求，则拒绝建立连接；反之则保留连接所需的多种资源，避免拥塞发生。

数据报中的拥塞控制

• 抑制分组 (Choke Packet)：
  每个路由器监视本节点的资源利用情况，若某个方向的资源利用率超过一定的门限，则该路由器向有关源节点发送抑制分组，源节点相应减少发往该方向的数据量，直至该方向的拥塞解除。

• 随机早期检测 (RED)：
  路由器维护一个运行队列长度的平均值。当某条链路上的平均队列长度超过某个阈值时，该链路就被认为即将拥塞，路由器随机丢弃一小部分数据包。

服务质量

从一个源端发到一个接收方的数据包流称为一个流。 - 面向连接网络：一个连接上的全部数据包。
- 无连接网络：从一个进程发到另一个进程的所有数据包。

每个流要求的服务质量 (QoS) 可由四个主要参数来表示： - 带宽 - 延迟 - 抖动：延迟的变化或数据包到达时间的变化 - 丢失

网络互连

网络如何不同

网络如何连接

• 源端接受来自传输层的数据，并生成一个带有公共网络层的头（IP头）。
  网络层的头包含了最终的接收方地址，这个地址用来确定数据包应该通过第一个路由器发送。

• 数据包被封装在 802.11 帧内，帧的目标地址是第一个路由器的地址。

• 在路由器，数据包从帧的数据字段中被提取出来，802.11 帧头被丢弃。
  路由器检查数据包的 IP 地址，并依此决定将数据包转发给第二个路由器。

• 第一个路由器建立一条到第二个路由器的 MPLS 虚电路，并且用 MPLS 报头封装该数据包。

• 在远端，MPLS 头被丢弃，并在此检查 IP 地址以便寻找下一跳网络层。

互联网路由

采用两级路由算法。
在每个网络中，使用一个域内或内部网关协议进行路由。
为了让数据包跨越构成互联网的网络，需要域间或外部网关协议。

网络可能全部使用不同的域内协议，但必须使用相同的域间协议。

在 Internet 上，域间路由协议称为边界网关协议 (BGP)。

自洽系统 (AS)：每个网络都独立于所有其他网络运行。

数据包分段

路径最大传输单元 (MTU)。

透明分段

当一个超大的数据包到达 G1，该路由器将它分割成多个段；每个段都发向同样的出口路由器 G2，在这里这些段被重新组合起来。

问题： - 每个分段中必须提供一个计数字段或者一个数据包结束标志位。 - 所有数据包必须经过同一个出口路由器才能重组，路由受到限制，损失一些性能。 - 路由器需要做大量的工作。

不透明分段

IP 采用这种方式工作。
给每个段一个数据包序号、一个数据包内的绝对字节偏移量和一个指明是否到达数据包末尾的标志位。段到达目的地后被放置在一个缓冲区中以便重组

问题： - 增加头开销。 - 数据包的丢失概率增加。

路径 MTU 发现

每个 IP 数据包发出时在头设置一个比特，指示不允许对该数据包实施分段操作。
如果一个路由器接收的数据包太大，它就生成一个报错数据包并发给源端，然后丢弃该数据包。
当源端收到报错数据包，它就使用报错数据包携带的信息重新将出错数据包分段，每个段足够小到报错路由器能处理。
如果沿路径前进又遇到一个 MTU 更小的路由器，则重复上述过程。

Internet 的网络层

Internet 是一个基于 IP 的分组交换网络，根据 IP 协议信息（主要是目的地址）来转发分组。

IP 提供尽力传送 (best-effort) 服务 - 不可靠：无连接，无确认；不保证分组可靠到达目的地，可能出现分组的丢失。 - 乱序：分组可能不是按照发送顺序到达目的地。

所有接入到 Internet 的节点都必须运行 IP 协议。
- 向上，可以互联采用各种通信技术的网络； - 向下，可以承载各种类型网络业务。

IPv4 协议

每个 IP 数据报包含两部分，一个头和一个正文（有效净荷）。头由一个20字节的定长部分和一个可选的变长部分组成。

IP 数据报头依次有： - 版本 (Version)：4-bit
记录数据报属于协议的哪个版本。
IPv4 填 4，IPv6 填 6。

• IHL：4-bit
  指明头的长度。
  IHL 的最小值为 5，表明头没有可选项；最大值为 15，把头的长度限制为最大 60 字节。

• 区分服务 (Differentiated services)：8-bit

  • 最初称为服务类型 (Type of service)，包含 6 位。
    其中 3 位表示优先级，3 位代表主机最关心的是延迟、吞吐量或可靠性中的哪一种。
  • 现在，前 6 位用来标记数据包的服务类别，后 2 位用来携带显示拥塞通知信息。

• 总长度 (Total length)：16-bit
  描述数据报总长度，包括头和数据。
  最大长度是 65535 个字节。

• 标识 (Indentification)：16-bit
  用于让目标主机确定一个新到达的分段属于哪一个数据报。
  同一个数据报的所有段包含相同的标识值。

• 莫名其妙空了 1 位。

• DF (Don't Fragment)：1-bit
  不分段标志位，不允许路由器分割该数据报。
  可用于发现路径 MTU 过程中。

• MF (More Fragments)：1-bit
  更多的段标志位，使接收方知道什么时候一个数据报的所有分段都到达了。
  除了最后一个段以外其他所有段都要设置这一位。

• 分段偏移量 (Fragment offset)：13-bit
  指明了该段在当前数据报中的位置。
  除了数据报的最后一个段以外，其他所有段的长度必须是 8 字节的倍数。
  每个数据报的第一个段的偏移量为 0，后面的段为前面所有段数据总字节数除以 8。
  由于该字段有 13 位，所以每个数据报最多有 8192 个段。

• 生存期 (TTL)：8-bit
  用于限制数据包生存期的计数器。
  单位为秒，故最大生存期为 255 秒。
  在每一跳上该计数器递减，而且当数据报在一台路由器上排队时间较长时，该计数器必须多倍递减。递减到 0 时，该数据包就被丢弃。

• 协议 (Protocol)：8-bit
  表示高层协议类型，指明该将数据包交给哪个传输进程（如 TCP、UDP）。
  协议的编号在整个 Internet 是全球统一的。

• 头校验和 (Header checksum)：16-bit

  • 计算校验和：先将头校验和字段置为 0，然后将整个 IP 头以 16 位为单位相加求和，溢出的部分加回低位，再将结果取反，得到的数据填入头校验和字段。
    
  • 验算：当数据到达时，同样将整个 IP 头以 16 位为单位相加求和，溢出的部分加回低位后取反，得到的结果如果是 0 则通过校验。

• 源地址 (Source address)：32-bit
  表示源网络接口的 IP 地址。

• 目标地址 (Destination address)：32-bit
  表示目标网络接口的 IP 地址。

• 选项 (Options)：具有可变长度，最多为 40 字节。
  用于包含一些原设计中没有出现的信息，同时也用于将数据报头的长度填充到 4 字节的整数倍。

  • 安全 (Security)：指明了信息的秘密程度。
  • 严格源路由 (Strict source routing)：给出了从源到目标的完整路径。
    形式是一系列 IP 地址。数据报必须严格遵循这条路线向前传输。
  • 松散源路由 (Loose source routing)：要求数据包穿越所指定的路由器列表。
    要求按照表中的顺序前进，但是允许在途中经过其他路由器。
  • 记录路由 (Record route)：使沿途每个路由器附上自己的出口 IP 地址。
    便于系统管理员跟踪路由算法中的错误。
    最多只记录 9 个 IP 地址。
  • 时间戳 (Timestamp)：使沿途每个路由器附上自己的 IP 地址和 32 位时间戳。

IPv4 地址

Internet 上的 IP 地址由 IANA (互联网编号分配机构) 负责分配和管理。

IP 地址用于标识主机或网络设备（如路由器）的网络层地址，可用在 IP 数据包的 Source address 和 Destination address 字段，路由器根据目的 IP 地址转发分组。
注意，一个 IP 地址并不真正指向一台主机，而是指向一个网络接口。如果一台主机在两个网络上，它必须有两个 IP 地址。

IP 地址具有层次性，每个 32 位地址由高位的可变长网络（前缀）和低位的主机两部分数据组成。

IP 地址的书写方式是点分十进制表示法。
按此格式，4个字节中的每个写成十进制，取值范围从 0 到 255。
按照惯例，网络地址的书写格式是前缀 IP 地址后跟一个斜线，斜线后是网络部分的位长度。
eg. 32位十六进制地址 80D00297 写成 128.208.2.151。假设前缀包含 $2^8$ 个地址，即网络部分包含 $32 - 8 = 24$ 位，网络地址写成 128.208.0.0/24。

前缀/子网

同一网络上的所有主机的前缀是相同的。

• 简单地由长度表述。
  如 24 位前缀表示为 /24。

• 前缀长度相当于网络部分中 1 的二进制掩码，称为子网掩码。
  如 24 位前缀对应的子网掩码为 255.255.255.0。

子网划分：在内部将一个网络块分成几个部分供多个内部网络，但对外部世界仍然像单个网络一样。
分割一个大型网络得到的一系列结果网络，称作子网。

当数据包到达时，路由器会查看该数据包的目标地址，并检查它属于哪个子网。
具体操作：路由器把数据包的目标地址与每个子网的掩码进行 AND 操作，看结果是否对应于某个前缀。

IP 地址和 MAC 地址

• IP 地址在整个网络中标识不同的节点，而 MAC 地址在链路或者局域网内标识不同的节点。
• IP 地址包含有网络号（前缀），因此节点配置的 IP 地址与其所在的网络相关；而 MAC 地址与节点位置无关，因此一般事先固化在网络设备中。
• 数据帧在链路上传送使用 MAC 地址，源 MAC 地址为发送主机的网络接口的 MAC 地址，而目的 MAC 地址为同一链路上接收主机的网络接口的 MAC 地址。
• IP 分组在 Internet 中传输使用 IP 地址，源 IP 地址为发送 IP 分组主机的 IP 地址，而目的 IP 地址为接收 IP 分组主机的 IP 地址。
• 数据帧在不同链路上传输时，源和目的 MAC 地址变化，而源和目的 IP 地址不变。

区别： | MAC | IP | | --- | -- | | 物理地址（数据链路层地址） | 逻辑地址（网络层地址） | | 局部意义 | 全局意义 | | 随机获得 | 上级分配 | | 48位（如 08:00:39:00:2f:c3） | 32位（如 202.38.75.11）|

IP 寻址

路由表与转发表

• 路由表 (Routing Table)

  路由器根据分组的目的 IP 地址查找路由表，找出分组的下一个中继点。
  每一个路由器都有一个路由表。

  路由表每个表项至少包含两个内容：

  • 目的网络（网络号或前缀）/目的主机的地址
  • 下一跳地址

  在路由器上，一般通过路由协议来动态建立和维护路由表。

• 转发表 (Forwarding Table)

  与路由表相比，转发表包含了更多的信息。
  包括包含目的网络的网络号/目的户籍的地址、输出端口，以及一些 MAC 地址等信息。

  每个节点上都有转发表，节点根据转发表来转发分组。
  主机上的转发表一般是手动或者通过 DHCP 等动态配置。

• 路由表是网络设备（通常是路由器）上的数据结构。
  转发表是路由表的实际应用，是根据路由表中的信息生成的用于实际数据包转发的表格。

无类域间路由 (CIDR)

路由聚合：把多个小前缀的地址块合并成一个大前缀的地址块。
由此产生的较大前缀地址块有时称为超网。

无类域间路由：同样一个 IP 地址，一台路由器把它当成 /22 的一部分对待（其中包含 $2^{10}$ 个地址），而另一台路由器把它当作一个更大的 /20 的一部分对待（其中包含 $2^{12}$ 个地址）；每个路由器有相应的前缀信息。

分配地址时： - $2^n$个地址的块必须位于 $2^n$ 的字节边界上，即地址的后 n 位为 0。 - 先分配所需地址更多的地址块。 - 确定子网掩码：首地址和末地址的前几位是相同的。
分配 $2^n$ 个地址，则子网掩码的长度是 $32 - n$ - 全 0 和 全 1 的主机号地址一般不用于标识主机或路由器接口。

eg.
有一块地址从 194.24.0.0 开始，可用的 IP 地址有 $2^{13} = 8192$ 个，即该地址块到 194.24.31.255（后 13 位为 1）。
假设 A 需要 $2048 = 2^{11}$ 个地址，B 需要 $1024 = 2^{10}$ 个地址， C 需要 $4096 = 2^{12}$ 个地址。 | 区域 | 第一个地址 | 最后一个地址 | 地址数 | 前缀 | | --- | ---------- | ----------- | ------ | ---- | | C | 194.24.0.0 | 194.24.15.255 | 4096 | 194.24.0.0/20 | | A | 194.24.16.0 | 194.24.23.255 | 2048 | 194.24.16.0/21 | | B | 194.24.24.0 | 194.24.27.255 | 1024 | 194.24.24.0/22 | | 空余 | 194.24.28.0 | 194.24.31.255 | 1024 | 194.24.28.0/22 |

A、B、C 三个网络具有一个聚合前缀 192.24.0.0/19。

前缀允许重叠，规则是数据包按最具体的路由的方向发送，即具有最少 IP 地址的最长匹配前缀。

CIDR 的工作原理：
当一个数据包到达时，路由器扫描路由表以确定目的地是否在前缀的地址块内。
有可能多个具有不同前缀的表项得到匹配，在这种情况下，使用具有最长前缀的表项。
例如有一个匹配 /20 掩码的表项，同时还有一个匹配 /24 掩码的表项，则使用 /24 表项来查询数据包的出境线路。

分类和特殊寻址

分类寻址：IP 地址被分为以下五个类别。 | 类别 | 位数划分 | 主机地址范围 | 网络数量 | 每个网络可容纳主机数 | | ---- | ------- | ----------- | -------- | ----------- | | A 类 | 最高位，0；
网络号，随后 7 位；
主机号，最后 24 位 | 1.0.0.0 到
127.255.255.255 | $2^7 -2$ | $2^{24} - 2$ | | B 类 | 最高两位，10；
网络号，随后 14 位；
主机号，最后 16 位 | 128.0.0.0 到
191.255.255.255 | $2^{14} -2$ | $2^{16} - 2$ | | C 类 | 最高三位，110；
网络号，随后 21 位；
主机号，最后 8 位 | 192.0.0.0 到
223.255.255.255 | $2^{21} - 2$ | $2^8 -2$ | | D 类 | 最高四位，1110；
是组播地址 | 224.0.0.0 到
239.255.255.255 | | | | E 类 | 最高四位，1111；
是保留地址 | 240.255.255.255 到
255.255.255.255 | | |

具有特殊含义的地址： - IP 地址 0.0.0.0 / 全 0 的 IP 地址：指当前网络/当前主机。
这个地址允许机器在不知道网络号的情况下访问自己所在的网络（但它们必须知道子网掩码包括多少个 0）。

• IP 地址 255.255.255.255 / 全 1 的 IP 地址：标识指定网络的所有主机。
  用于广播。

• 127.xx.yy.zz 形式的地址：保留给回环测试用。
  发送到该地址的数据包并没有被真正放在线路上，它们如同入境数据包一样在本地处理。

NAT

网路地址转换 (NAT)：实现网络内多个主机共享一个全局的 IP 地址。
基本思想：
ISP (互联网服务提供商) 为每个家庭或公司分配一个（或少量）IP 地址，用这个 IP 地址来传输 Internet 流量。
在客户网络内部，每台计算机有唯一的 IP 地址，该地址主要用来路由内部流量。
当一个数据包需要离开客户网络，需要执行一个地址转换，把唯一的内部 IP 地址转换成共享的公共 IP 地址。

内部网地址有： - 10.0.0.0 - 10.255.255.255 - 172.16.0.0 - 172.31.255.255 - 192.168.0.0 - 192.168.255.255

NAT 技术可以在路由器、防火墙上实现内外地址的翻译工作。
实现方式： - 静态 NAT：
内部地址与外部 IP 地址总是一一对应的。
如 192.168.32.10（内部地址） 总是翻译成 213.18.123.110（外部地址）。

• 动态 NAT：
  一组全局 IP 地址与内部 IP 地址对应。
  如 192.168.32.10 总是翻译成 213.18.123.100 到 213.18.123.150 范围内第一个可用的 IP 地址。

• 网络地址端口转换 (NAPT)：
  也是一种动态方式，用一个全局 IP 地址加上端口号实现与内部 IP 地址的翻译。

  • 内部主机访问互联网：
    • 假设公共 IP 地址为 203.0.113.1。
    • 内部主机 A 要访问一个网站，于是发起一个请求到该网站的服务器。
    • NAPT 检测到主机 A 的请求，将主机 A 的内部 IP 地址 192.168.1.1 和一个唯一的端口号 5001 关联起来。
    • NAPT 修改主机 A 的请求，将源 IP 地址改为 203.0.113.1，源端口号改为 5001，然后将修改后的请求发送到互联网。
  • 互联网服务器响应：
    • 互联网服务器收到请求后，将响应发送回 203.0.113.1:5001。
    • NAPT 根据会话表确定这个响应该被转发给内部主机 A。
    • NAPT 修改响应，将目标 IP 地址和端口号还原为主机 A 的内部 IP 地址和端口号，然后将响应发送给主机 A。

IPv6 协议

IPv6 头依次有： - 版本 (Version)：4-bit

• 区分服务 (Differentiated services)：8-bit
  使用方式与 IPv4 同名字段一样。

• 流标签 (Flow label)：20-bit
  为源端和接收方提供了一种建立伪连接的方式，即源端和接收方把一组具有同样需求并希望网络同等对待的数据包打赏标记。
  每个流由源地址、目标地址和流编号来指定。
  流标签的选取最好随机，便于路由器对它们进行哈希处理。

• 有效荷载长度 (Payload length)：16-bit
  与 IPv4 中的总长度字段，但是 40 字节的头不作为长度的一部分。

• 下一个头 (Next header)：8-bit
  指明了当前头之后还有哪种扩展头，如果有的话。
  如果当前的头是最后一个 IP 头，那么该字段指定了该数据包将被传递给哪个传输协议处理（如 TCP、UDP）。

• 跳数限制 (Hop linit)：8-bit
  与 IPv4 中的 TTL 字段类似，但不再是以秒为单位。

• 源地址 (Source address)：16 字节

• 目标地址 (Destnation address)：16 字节

扩展头

IPv6 地址

16 个字节被分成 8 组来书写，每一组 4 个十六进制数字，组之间用冒号隔开。
如 8000:0000:0000:0000:0123:4567:89AB:CDEF

优化方式： - 在一个组内可以省略前导 0。 - 一组或多组 0 可以用一对冒号来替代。
故上述地址可以写成 8000::123:4567:89AB:CDEF

地址前缀表示：IPv6 地址/前缀长度

与 IPv4： - 兼容 IPv4 的 IPv6 地址：
IPv4 地址写成一对冒号再加上老式的点分十进制数。
如 ::192.31.20.46
- 映射 IPv4 的 IPv6 地址：
将 80 位 0 和随后的 16 位 1 组成的前缀置于 IPv4 地址之前。
如 ::FFFF:192.31.20.46 - IPv6 默认情况下禁用 IPv4 兼容地址。

IPv6 地址即插即用。
工作原理：自动将 48 位 MAC 地址扩展成 64 位，再组合一个 64 位的 IPv6 网络前缀，组成一个 IPv6 地址。
IPv4 的 64 位接口地址可以根据 MAC 地址自动生成，属于 IEEE EUI-64 标准。

分类

• 单播地址

  • 可聚类全局地址 2000::/3
    • 3 位前缀：001
    • 13 位顶级聚类：TLA
    • 32 位次级聚类：NLA
    • 16 位网点级聚类：SLA
    • 64 位接口标识符：Interface ID
  • 本地（局域）单播地址
    • 链路局域地址 FE80::/64
      包含 64 位前缀和之后的 64 位接口标识符。
      用于本地链路上各个相邻接口之间的发现、IPv6 地址自动配置和通信。
      包含链路局域地址的分组不会被路由器转发。
    • 网点局域地址 FEC0::/48
      包含 48 位前缀，16 位子网 ID，64 位接口标识符。
      只可以再一个网点内使用。

• 未指明地址 0:0:0:0:0:0:0:0 或表示为 ::
  只能作为尚未获得正式地址的主机的源地址使用，不能将该地址用作信宿地址。

• 环回地址 0:0:0:0:0:0:0:1

• 组播地址
  前 8 位为 1，4 位标志位（000T，T=0 表示永久性组地址），4 位区域位，112 位 Group ID。

• 任播地址：从单薄地址空间中分配
  前 n 位为子网前缀，后 128-n 位为 0。

Internet 控制协议

ICMP

Internet 控制消息协议 (ICMP)：当路由器在处理一个数据包的过程中发生了意外，通过 ICMP 向数据包的源端报告有关事件。

ICMP 定义了两类报文，差错报文和信息报文： - 差错报文 - 源抑制 (Source quench)：抑制发送过多分组的主机。 - 超时 (Time exceeded)：分组的 TTL 为 0，或被分片的报文在一定时间内没有收齐。 - 信宿不可达 (Destination unreachable)：报告子网、主机不能定位的信宿。 - 重定向 (Redirect)：数据包看起来被错误地路由。 - 参数问题 (Parameter problem)：分组头参数出错。

• 信息报文
  • 回音请求/响应 (Echo request/reply)
  • 地址掩码请求/响应 (Address mask request/reply)
  • 路由器发现 (Router discovery)

ICMP 的直接应用： - Ping Progarm 用于测试主机的可到达性。
Ping 程序采用 ICMP 的回音请求/响应报文，通过向信宿发送回音请求，返回响应报文，来测试目的主机的可达性。

• Traceroute
  通过发送递增的 TTL 值的回音报文，测试目的主机沿途经过的路由器地址。

ARP

地址解析协议 (ARP)：解析 IP 地址与 MAC 地址的关系。

• 目的 IP 地址所对应的主机和发送主机在同一个网络内。

  • 每个主机都有 ARP 缓存，用于存放一些 IP 地址与 MAC 地址的对应关系。
    通过 ARP 缓存可以减少频繁的 ARP 操作，从而减少网络开销、提高性能。

  • 当分组到达时，主机根据分组头上的目的 IP 地址查阅自己的 ARP 缓存；如果没有查到，就向广播地址发送 ARP 请求。

  • 被请求的 IP 地址所对应的主机返回一个 ARP 响应。

  • 主机收到响应后，就可发送数据帧，并将该 IP 地址与 MAC 地址对存放在 ARP 缓存中。

• 目的 IP 地址所对应的主机和发送主机在两个不同的网络内。

  • 发送主机通过查找转发表得到下一跳节点的 IP 地址（第一跳路由器），对该 IP 地址执行上述 ARP 过程，然后发送数据。

  • 发送主机也可以直接用目的 IP 地址执行 ARP，路由器（而不是目的主机）响应该 ARP 请求。
    这种解决方式叫 ARP 代理。

  • 第一跳路由器查找转发表得到第二跳路由器的 IP 地址，对该 IP 地址执行 ARP 过程，然后发送数据。
    $\cdots$
    目的网络的路由器查找转发表知道目的节点和自己在同一个网络中，对目的 IP 地址执行 ARP 过程，然后将数据发送到目的节点。

  • ARP 过程被限制在同一个网络内，始终是查找转发表得到转发下一跳节点的 IP 地址，然后对该 IP 地址做 ARP。
    在数据传输频繁时，ARP 缓存表中一般有对应的表项，节点间不需要交互 ARP 过程。

反向 ARP (RARP)：用于查找物理地址所对应的 IP 地址。

帧格式为 802.3 帧格式

• 前导码 (Preamble)：8 字节

• 目标 MAC 地址：6 字节

• 源 MAC 地址：6 字节

• 帧类型 (Type)：2 字节
  ARP 请求及响应为 0x0806

• 数据：

  • 硬件类型：2 字节。指发送者的网络接口类型，如以太网为 1。
  • 上层协议类型：2 字节。指发送者所采用的网络层协议类型，如 IP 协议为 0x0800。
  • MAC 地址长度：1 字节
  • IP 地址长度：1 字节
  • 操作类型：2 字节
    • ARP 请求：1
    • ARP 响应：2
    • RARP 请求：3
    • RARP 响应：4
  • 源 MAC 地址：6 字节
  • 源 IP 地址：4 字节
  • 目的 MAC 地址：6 字节
  • 目的 IP 地址：4 字节

• 填充

• 校验和：4 字节，CRC。

DHCP

IP 地址的配置方式有： - 手动配置 - 拨号用户通过 PPP 协议分配 - 基于动态主机配置协议 (DHCP) 的配置

DHCP 过程： - 客户端广播 DHCPDISCOVER 消息。
源 IP 地址为 0.0.0.0，目的 IP 地址为 255.255.255.255。
使用 MAC 地址来标识客户端。

• DHCP 服务器回应 DHCPOFFER 消息给客户端，其中包含分配的 IP 地址、租用期限和其他配置参数。

• 客户端选择一个 DHCP 服务器并在整个网络上广播 DHCPREQUEST 消息，告诉其他 DHCP 服务器它选择哪个服务器提供的 IP 地址。

• 选定的服务器给客户端回应 DHCPACK，其中包含配置参数。

• 客户端接收 DHCPACK，对参数进行最后的检查，然后开始使用分配的 IP 地址。

• 客户端可以通过向 DHCPRELEASE 消息来释放对 IP 地址的租用，其中包含有客户端的 MAC 地址和租用 IP 地址。

Internet 路由协议

自洽系统 (Autonomous System)： - 内部管理由独立管理机构完成的一组网关和网络，整个网络由一个（或几个）核心网关与 Internet 相连。 - 交换路由信息的两个网关如果属于不同的自洽系统，则称这两个网关是外部相邻；
如果同属于一个自洽系统，则称为内部相邻。

外部网关协议 (EGP)：用于外部相邻的网关之间交换路由信息，也叫域间路由。(BGP)
内部网关协议 (IGP)：用于内部相邻的网关之间交换路由信息，也叫域内路由。(RIP, OSPF)

RIP

路由信息协议 (RIP)：一种内部网关协议。

特点： - 采用距离矢量路由算法。

• 使用跳数 (hop count)，即路由器到目的地的路径中经过的路由器数量，作为衡量路径长度的单位。

• 通过 Split Horizon 机制防止路由环路的产生。
  即路由器不会将它已经学到的路由信息再发送回相同的接口。

• 路由器周期性地广播它们的整个路由表，以便告知其他路由器当前网络的可达性。
  该广播过程通过 RIP 更新报文完成。

• 使用 Hold-down Timer 来减少路由表更新引起的不稳定。
  当路由器检测到某个网络不可达时，它启动 Hold-down Timer，阻止对该网络的更新。

• 使用 UDP 在端口 520 上进行发送和接收路由信息。

OSPF

开放最短路径优先 (OSFP)：一种内部网关协议。
借鉴了中间系统到中间系统 (IS-IS) 协议，该协议已经成为一个 ISO 标准。

特点： - 是一种链路状态协议，采用最短路径优先算法 (SPF)。

• 使用 IP 作为底层传输协议，其中 IP 头的协议字段为 89，表示该数据包用于传输 OSPF 信息。

• 只有当发生改变时才更新路由表.

• 要求从每个 LAN 中选举一台路由器作为指定路由器 (DR)。
  指定路由器与本 LAN 上所有其他路由器是邻接的，并且与它们交换信息。
  有一台备份的指定路由器 (BDR) 总是保持最新的状态数据。

• 使用组播地址来发送 Hello 消息和路由更新。
  OSPFv2 使用组播地址 224.0.05（所有 OSPF 路由器）和 224.0.06（DR 和 BDR 选举）
  OSPFv3 使用组播地址 FF02::5（所有 OSPF 路由器）和 FF02::6（DR 和 BDR 选举）

5 种数据包： | 消息类型 | 描述 | | ------- | ----- | | Hello | 用来发现所有的邻居 | | Link State Update | 提供发送者到其邻居的成本 | | Link State Ack | 对链路状态更新消息的确认 | | Database Description | 声明发送者的链路状态更新情况 | | Link State Request | 请求链路状态信息 |

BGP

边界网关协议 (BGP)：一种外部网关协议。

特点： - 路径矢量协议 (path vector protocol)
升级版距离矢量协议。
根据政策而不是最小距离来选择路由。
路由器不仅维护到每个目的地的成本，而且跟踪所使用的路径。

• 使用 TCP 协议来保障可靠性，使用端口 179。

• 使用增量和触发式更新方式。
  当网络拓扑发生变化时，只有受到触发事件影响的路由信息才会被更新。

• 定期发送保持活动消息以验证 TCP 连接的连通性。

• 使用丰富的指标（路径矢量/属性）来描述和选择路由。
  包括 AS 路径、AS 路径长度、下一跳等信息。

• 设计用于大规模网络，如 Internet。

路由协议分类与协议栈

路由协议分类： - 基于路由信息流的分类
- 内部网关协议 (IGP) / 域内协议 - RIP - OSPF - IS-IS - 外部网关协议 (EGP) / 域间协议 - BGP

• 基于确定路由表所使用的信息类型的分类
  • 距离矢量路由协议
    • RIP
    • BGP
  • 链路状态路由协议
    • OSPF
    • IS-IS

协议栈： | 层 | 协议 | | | | | :-: | :-: | :-: | :-: | :-: | | 应用层 | BGP | RIP | | | | 传输层 | TCP | UDP | OSPF | | | 网络层 | IP | IP | IP | IS-IS | | 链路层 | | | | | | 物理层 | | | | |

Internet 组播

• 单播 (unicast)：1 对 1

• 组播 (multicast)：1 对多，多对多

  • IP 采用 D 类地址作为组播地址。
    每个 D 类地址代表一组主机，共有 28 位可用来标识小组。

  • Internet 支持两类组地址：永久组地址和临时组地址。

    • 永久组地址：

      IP 地址 224.0.0.0/24 范围内的地址保留用作本地网络组播。
      这种情况下不需要路由协议的支持，带有一个组播地址的数据包被简单广播到局域网上。
      局域网上的所有主机接收广播数据包，只有属于组成员的主机对该数据包进行处理。

      • 224.0.0.1：LAN 上的全部系统
      • 224.0.0.2：LAN 上全部路由器
      • 224.0.0.5：LAN 上全部 OSPF 路由器
      • 224.0.0.251：LAN 上全部 DNS 服务器

    • 临时组地址：

      需要路由协议，组播路由器需了解哪些主机属于某个组。

      Internet 组管理协议 (IGMP)：

      • 一个进程要求它的主机加入某个指定的组/离开该组。每台主机跟踪记录当前它的进程属于哪些组。当一台主机上的最后一个进程离开一个组时，该主机就不再属于这个组。
        
      • 每个组播路由器定期向它所在 LAN 上的所有主机（使用 224.0.0.1）发送一个查询数据包，要求这些主机报告自己当前属于哪些组。
        
      • 每个主机收到查询消息后，返回一个响应包，包括了自己感兴趣的所有 D 类地址。

• 广播 (broadcast)：1 对多

• 任播 (anycast)：1 对多中的一个

组播路由协议

数据包沿着生成树发送，通过修建广播生成树把不通往组成员的链路从树中删掉，得到一棵有效的组播生成树。

• 基于源的组播协议：以发送方为多播树的根，并且包含了所有的组成员。
  • 距离矢量组播路由协议 (DVMRP)
  • 组播 OSPF (MOSPF)
• 基于共享树的协议：对每个组使用同一颗树。
  • 基于核心树 (Core Based Trees)
• 混合以上两种方法的协议
  • 协议独立组播协议 (PIM)
    • 密集模式 PIM (PIM-DM)：创建一颗修建的逆向路径转发树。
    • 稀疏模式 PIM (PIM-SM)：创建的生成树类似于核心树。

第3章 数据链路层

• 基本概念与功能
  • 基本概念
  • 功能
  • 提供给网络层的服务
  • 成帧
  • 差错控制
  • 流量控制
• 差错检测和纠正
  • 纠错码
    • 海明码
    • 卷积码
    • 里德所罗门码
    • 低密度奇偶校验码(LDPC)
  • 检错码
    • 奇偶
    • 校验和
    • 循环冗余校验码(CRC) / 多项式编码
• 基本数据链路层协议
  • 无限制的单工协议
  • 无错信道上的单工停-等式协议
  • 有错信道上的单工停-等式协议
• 滑动窗口协议
  • 回退N协议(出错全部重发协议)
  • 选择重传协议
• 数据链路层协议实例
  • 高级数据链路控制(HDLC)
    • HDLC 帧格式
  • 点到点协议(PPP)
    • PPP 帧格式
    • 与HDLC比较

基本概念与功能

基本概念

链路：连接相邻节点的通信信道，中间没有任何其他的交换节点。 - 点对点链路：链路的两端都只有一个节点，一个节点发送，另一个节点接收，带宽独占。 - 点对多点链路（广播链路，共享链路）：链路上有多个节点，带宽共享，需要媒体访问控制(MAC)机制来控制多个用户对信道的访问。

通信方式： - 单工通信：指消息只能单方向传输的工作方式。 - 半双工通信：指数据可以沿两个方向传送，但同一时刻一个信道只允许单方向传送。 - 全双工通信：指在通信的任意时刻，两个节点间可以同时双向传输信号。
TDD(时分双工)是移动通信中上下行在同一频段上按照时间分配交叉进行传输。
FDD(频分双工)是指上下行在不同频段同时进行传输。

功能

数据链路层使用物理层提供的服务在通信信道上发送和接收比特。
1. 向网络层提供一个定义良好的服务接口。
2. 将物理层的比特流编成帧。 3. 处理传输错误。（差错控制）
4. 调节数据流，确保慢速的接收方不会被快速的发送方淹没。（流量控制）

提供给网络层的服务

• 无确认的无连接服务
  源机器向目标机器发送独立的帧，目标机器并不对这些帧进行确认。eg. 以太网
  适用于错误率很低的场合及实时通信。

• 有确认的无连接服务
  数据链路层仍然没有使用逻辑连接，但发送的每一帧都需要单独确认。eg. 802.11
  适用于不可靠信道，如无线系统。
  

• 有确认的有连接服务
  常用于广域网，如帧中继等。
  数据传输经过三个阶段：

  • 建立连接，双方初始化各种变量和计数器；
  • 传输一个或多个数据帧，每一个帧都被编号，保证传送的帧被对方收到，且只收到一次；
  • 释放连接。

成帧

将比特流拆分成多个离散的帧，为每个帧计算一个校验和，并将该校验和放在帧中一起传输。

• 字节计数法
  利用头部中的一个字段来标识该帧中的字符数。

  缺点：出错之后无法重新同步。

• 字节填充的标志字节法
  在帧的起始和结尾用特殊的字节标志，这些特殊字节称为标志字节。

  当标志字节出现在数据中时，发送方在出现的每个标志字节前插入一个特殊的转义字节，接收方的数据链路层在将数据传递给网路层之前删除转义字节。
  如果转义字节出现在数据中，即用另一个转义字节填充。在接收方值删除第一个转义字节。

  缺点：只能使用8比特的字节。

• 比特填充的标志比特法（位标志）
  用特殊的位序列表示帧的起始和结尾，如01111110或0x7E。
  每当发送方的数据链路层在数据中遇到连续5个1，就自动在输出的比特流中填入一个0。
  当接收方看到5个连续入境的比特1，并且后面紧跟着一个比特0，就自动剔除这个比特0。

  原始数据	发送数据	接收方存储数据
  011011111110	0110111110110	011011111110

  优点：确保了转换的最小密度，有助于物理层保持同步。eg. USB
  缺点：和字节填充一样，受标志字节出现数量的影响，帧的长度取决于它所携带的数据内容。

• 物理层编码
  在物理层用1.5或2个物理位表示一个数据位来表示帧的起始与结尾。

差错控制

要求接收方发回特殊的控制帧，在控制帧中对它所接收到的帧进行肯定或否定的确认。

当发送方发出一帧时，启动一个计时器。该计时器的超时值设置得足够长，保证在正常情况下该帧能够到达接收方，并且在接收方进行处理后再将确认返回到发送方。计时器超时后，发送方重新发送该帧。

发送方给发出去的帧分配序号，以便接收方根据序号来有效区分原始帧和重传帧。

流量控制

• 基于反馈的流量控制：接收方给发送方返回信息。
  
• 基于速率的流量控制：存在内置的机制，能限制发送方传输数据的速率，无需反馈信息。

差错检测和纠正

纠错码

一帧由 m 个数据位（信息）和 r 个冗余位（校验）组成。
块码：r 个校验位由与之相关的 m 个数据位的函数计算获得。
系统码：直接发送 m 个数据位，然后发出 r 个校验位。
线性码：r 个校验位是作为 m 个数据位的线性函数被计算出来的。

令数据块的总长度为 n，即 n = m + r。
n 位码字：一个包含了数据位和校验位的n位单元。
码率：码字中不包含冗余部分所占的比例，即 m/n。

海明码

海明距离：两个码字中不相同的位的个数。
码字集合的海明距离：码字集合中任意两个有效码字间的最小海明距离。

如果两个码字的海明距离为 d，则需要 d 个一位错误才能将一个码字转变成另一个。
为了可靠地检测d个错误，需要一个距离为 d+1 的编码方案（相邻码字的距离为 d+1）。
为了纠正 d 个错误，需要一个距离为 2d+1 的编码方案。

在给定 m 的情况下，纠正单个错误所需要的校验位数下界：
$$(m + r + 1) \leq 2^r$$

以传输 1000001 为例：

• 发送方：

  • 数据位为 7 位，计算 $(7 + r + 1) \leq 2^r$，解得 r = 4，故编码共有 11 位。
    海明码中，所有位从左到右由1开始依次编号，其中2的幂次方位是校验位，其余为数据位。
    在本例中，第 1、2、4、8 位为校验位。
    在校验位中先填上 0，其余位依次填充 1000001，即 00100000001。

  • 将位的序号改写成 2 的幂次之和，即换算成二进制形式。校验位覆盖二进制形式序号对应位为 1 的数据位。
    即第 1 位校验第 (1, 3, 5, 7, 9, 11) 位，第 2 位校验第 (2, 3, 6, 7, 10, 11) 位，第 4 位校验第 (4, 5, 6, 7) 位，第 8 位校验第 (8, 9, 10, 11) 位。

    将每个校验位所覆盖的位对应的值逐一异或，即可得到该校验位应该填入的值:
    第 1 位: $0 \oplus 1 \oplus 0 \oplus 0 \oplus 0 \oplus 1 = 0$
    第 2 位: $0 \oplus 1 \oplus 0 \oplus 0 \oplus 0 \oplus 1 = 0$
    第 4 位: $0 \oplus 0 \oplus 0 \oplus 0 = 0$
    第 8 位: $0 \oplus 0 \oplus 0 \oplus 1 = 1$

    序号	二进制形式 8421	计算前的值	发送的值
    1	0001	0	0
    2	0010	0	0
    3 = 1+2	0011	1	1
    4	0100	0	0
    5 = 1+4	0101	0	0
    6 = 2+4	0110	0	0
    7 = 1+2+4	0111	0	0
    8	1000	0	1
    9 = 1+8	1001	0	0
    10 = 2+8	1010	0	0
    11 = 1+2+8	1011	1	1

  • 故发送的码字为 00100001001。

• 接收方：

  • 假设传输过程中发生错误，收到的码字为 00101001001。

  • 重新计算校验位：
    第 1 位: $0 \oplus 1 \oplus 1 \oplus 0 \oplus 0 \oplus 1 = 1$
    第 2 位: $0 \oplus 1 \oplus 0 \oplus 0 \oplus 0 \oplus 1 = 0$
    第 4 位: $0 \oplus 1 \oplus 0 \oplus 0 = 1$
    第 8 位: $0 \oplus 0 \oplus 0 \oplus 1 = 1$

  • 将重新计算得到的校验位与收到码字中的校验位比较（位数从高到低排列）。
    即将 1101 与 1000 按位异或，得到 0101 (即二进制形式的 5)。
    这意味着同时被第 1、4 位覆盖的位发生了错误，即第 5 位发生了错误。
    将该位反转可以得到正确的码字：00100001001。

from zy：

• 海明码的编码距离为 3。
• 海明码可以检出所有$\leq 2$ 比特的错误，且可以纠正 1 比特错误。

卷积码

编码器有内存，处理一个输入位序列并生成一个输出位序列。
约束长度：决定当前输出的以前输入位数。
卷积码由它们的速率和约束长度来标识。

里德所罗门码

线性块码，往往也是系统码。

基于m位符号（1位错误和m位突发错误都只作为一个出错的符号处理）。
加入2t个冗余符号后，能够纠正传输符号中的任意t个错误。

低密度奇偶校验码(LDPC)

线性块码。

每个输出位由一小部分的输入位形成。接收到的码字通过一个近似算法解码获得。

检错码

以下检错码均为线性的系统块码。

奇偶

奇校验/偶校验：将所有位逐一异或，得出结果为 0 说明该码字中共有偶数个 1；偶校验则再填入一个 0，奇校验则再填入一个 1。
可以检出1位错误。

plus版：将发送的每个数据块作为一个n位宽和k位高的长方形矩阵来处理。
交错检验：以不同于数据位发送的次序来计算校验位。

为n列中的每列计算校验位，按k行发送全部的数据位，发送次序是从上到下发送每一行，行内数据位通常按从左到右的次序发送，在最后一行发送n个校验位。
这种方法对于nk长度的数据块使用了n个校验位，可以检出一个长度小于等于n的突发错误。

校验和

通常指与信息相关的一组校验位。

• Internet校验和
  按16位字计算得出的消息位总和，后续的 IP 头中包含有具体计算方法。
  缺点：检测不到0数据的增加或删除；检测不出消息中被替换的部分；对两个数据包拼接起来的消息只有弱保护作用。

• Fletcher校验和
  包括一个位置组件，将数据和其位置的乘积添加到总和中。

循环冗余校验码(CRC) / 多项式编码

将位串看作系数是0或1的多项式。一个k位帧看作是一个k-1次多项式，从$x^{k-1}$到$x^0$。

运算规则：加法和减法都等同于异或。

假设一帧有m位，对应于多项式$M(x)$
生成多项式：$G(x)$

计算CRC的算法：
- 假设$G(x)$的阶为r。在帧的低位端加上r个0位，对应多项式$x^r M(x)$。
- 利用模2除法，用对应于$x^r M(x)$的位串除以对应于$G(x)$的位串。
- 利用模2减法（实际上就是异或），从对应于$x^r M(x)$的位串中加上余数。结果就是将被传输的带校验和的帧，其多项式记为$T(x)$。
- 如果收到的多项式可以除尽生成多项式，则证明传输正确。

eg.
帧：1101011111 对应多项式 $M(x) = x^9 + x^8 + x^6 + x^4 + x^3 + x^2 + x + 1$
生成多项式：10011 对应 $G(x) = x^4 + x + 1$
用 $x^4 M(x) \div G(x)$，得到商为 1100001110、余数为 10。
发出的帧对应多项式 $T(x) = x^4 M(x) + x$，即发送的帧为 11010111110010。
此时 $T(x)$ 可以被 $G(x)$ 整除。

• 带r个校验位的多项式编码可以检测到所有长度小于等于r的突发错误。
  
• 当突发错误的长度为r+1时，通过检测的概率是$\dfrac{1}{2^{r-1}}$。
  
• 当突发错误的长度大于r+1或者几个短突发错误发生时，通过检测的概率为$\dfrac{1}{2^r}$。

eg. 几乎所有的局域网（以太网/802.11）和点到点链接（SONET上的数据包）。

基本数据链路层协议

无限制的单工协议

理想条件：
- 数据单向传输，收发双方的网络层一直处于就绪状态。
- 处理时间可忽略不计，接收缓冲空间无限大（无需任何流量控制）。
- 信道不会损坏或丢失帧（无需任何差错控制）。

发送过程：运行在源机器的数据链路层上。
- 从（总是就绪的）网络层获取一个数据包。
- 构造一个出境帧。
- 通过物理层发送该帧。

接收过程：运行在目标机器的数据链路层上。
- 等待事件（到达了一个完好无损的帧）发生。
- 帧到达后，将新到达的帧从硬件缓冲区中删除，并放到一个变量中。
- 将该帧的数据部分传递到网络层。

无错信道上的单工停-等式协议

停-等式协议：发送方发送一帧，等待对方确认到达后才能继续发送。

条件：与理想条件不同的是，接收端需要一定的接收处理时间，接收缓冲只能存放一个帧。

• 为了防止发送快于接收而造成数据丢失，发送端发送一帧后必须停止发送，等待接收端发回的反馈确认。
  
• 接收端在收到一个帧并发送网络层后，需向发送端发一反馈确认短帧，表示可发新帧。
  
• 由于需要反馈，且帧的发送和反馈是严格交替进行的，所以相当于采用半双工信道。

有错信道上的单工停-等式协议

自动重复请求(ARQ) / 带有重传的肯定确认(PAR)：发送方在前移到下一个数据之前必须等待一个肯定确认的协议。

条件：与无错信道上的条件不同的是，通信信道可能会出错，帧可能被损坏，也可能完全被丢失。

• 增加一个计时器。
  应保证超时值足够长，确保帧到达接收方，按照最坏的情形被接收方所处理，然后确认帧被返回发送方所需要的全部操作时间。

• 增加一位序号。

发送过程： - 发送方在发出一帧后启动计时器。如果计时器已经在运行，则将它重置。 - 发送方等待相关事件发生。 - 如果到达了一个有效的确认帧，则发送方从它的网络层获取下一个数据包，并将它放入缓冲区覆盖掉原来的数据包，同时递增（0变1，1变0）帧的序号。
- 如果到达了一个受损的确认帧，或者计时器超时，则缓冲区和序号都不做任何改变。
- 发送缓冲区的内容。

接收过程：
- 一个有效帧到达时，接收方检查它的序号，确认是否为重复数据包。
- 如果不是重复数据包，则接收该数据包并传给网络层，然后生成一个确认帧。
- 如果是重复帧或受损帧，则不传递给网络层，且重复发送最后一个正确接收到的数据帧的确认。

滑动窗口协议

允许发送站连续发送多个帧而不需等待确认的做法称作管道化，属于一种窗口机制。

捎带确认：暂时延缓确认以便将确认信息搭载在下一个出境数据帧上的技术。
当一个按正常次序发送的数据帧到达接收方后，接收方启动一个辅助计时器。如果在计时器超时前，没有出现需要发送的反向流量，则发送一个单独的确认帧。
辅助计时器的超时间隔应明显短于与数据帧关联的计时器间隔。

累计确认：当n号帧的确认到达，n-1号帧/n-2号帧等都会被自动确认。
因此再实际网络中，ACK = n 一般表示现在期望接收第 n 号帧。

发送窗口尺寸：允许连续发送的帧的数量。
如果最大窗口为n，则发送方需要n个缓冲区来存放未被确认的帧，以满足可能的重传需要。

发送窗口：发送端允许不等确认而连续发送的帧的序号表。
当发送端收到发送窗口下沿帧的肯定确认时，将发送窗口整体向前滑动一个序号，并从输出缓冲区中将相应的数据帧副本删除。

接收窗口：接收端允许接收的帧的序号表。
- 对于落在窗口外面的帧：丢弃。 - 对于在窗口内但不是接收窗口下沿的帧：暂存在输入缓冲区
- 对于接收窗口下沿帧：将其连同后面连续的若干个检验过的正确帧按顺序交给网络层，在发回确认帧的同时将接收窗口向前滑动相应的数量。

发送窗口和接收窗口不必有相同的上下界，也不必有相同的大小。

带宽-延迟乘积：
$$BD = 单向延迟 \times 带宽$$
单项延迟的单位为s，带宽单位为bps，将乘积除以一帧对应的比特数，从而得到 BD 的单位为帧。

假设发射窗口为 w（帧）：
$$链路利用率 \leq \dfrac{w}{2BD + 1}$$

回退N协议(出错全部重发协议)

发送窗口的尺寸大于1，接收窗口的尺寸等于1。
发送端需要为每个待确认的帧都各自设置一个定时计数器。

• 接收端只能按顺序接受数据帧。
• 不在接收窗口内的帧到达时直接丢弃，不返回确认。
• 最终发送方超时并重新发送所有未被确认的帧。

如果帧序号用 n 位编码，则发送窗口尺寸为 $MAX\_SEQ \leq 2^n - 1$，即存在 $MAX\_SEQ + 1$ 个不同的序号。否则会造成接收端无法分辨新旧数据帧。

出错全部重发协议只要求发送端保持一定数量的缓存来保存没有确认的数据帧，对接收端没有缓存的要求。但在误码率高的情况下，会大大降低信道的利用率。

选择重传协议

发送和接收窗口的尺寸都大于1。

非顺序接收。接收端可存储坏帧之后的其它数据帧（落在接收窗口），接收端对错帧发否定确认帧 (NAK)，因此发送端只需重发出错的帧，而不需重发其后的所有后续帧。接收端正确收到重发的帧后，可对其后连续的已接收的正确帧作一次总体确认（累计确认），并交送网络层。

接收窗口的尺寸不能超过 $2^{n-1}$ (n 同样表示编码位数)，即序号空间的一半，否则可能造成帧的重叠。
发送窗口的尺寸一般和接收窗口的尺寸相同（两者相加 $\leq 2^n$）。

接收方所需缓冲区的数量等于窗口的大小。假设有n号缓冲区，当第i号帧到达时，它被放到 (i mod n) 号缓冲区中。
发送端为每一个输出缓存区设置一个定时计数器，需要定时器的数量等于缓冲区的数量。定时器一旦超时，相应输出缓存区中的帧就被重发。

数据链路层协议实例

高级数据链路控制(HDLC)

是由国际标准化组织制定的面向位的有序链路层协议。

是为非平衡的链路级操作而研制的，采用主从结构，链路上一个主站控制多个从站，主站向从站发命令，从站向主站返回响应。