计算机通信与网络

计算机通信与网络

前言

数据通信与网络课件

第一章 概述

1.1 第一讲 绪论

1.2 第二讲 网络模型

第二章 物理层和介质

2.1 第三讲 物理层

2.2 第四讲 数字传输

2.3 第五讲 模拟传输

2.4 第六讲 带宽利用

2.5 第七讲 传输介质

2.6 第八讲 交换

2.7 第九讲 使用电话网和有线电视网进行数据传输

第三章 数据链路层

3.1 第十讲 检错与纠错

3.2 第十一讲 数据链路控制

3.3 第十二讲 多路访问

3.4 第十三讲 有线局域网:以太网

3.5 第十四讲 无线局域网

3.6 第十五讲 连接局域网、主干网和虚拟局域网

3.7 第十七讲 广域网

3.8 第十八讲 虚电路网络:帧中断和ATM

第四章 网络层

4.1 第十九讲 逻辑寻址

4.2 第二十讲 IP协议

4.3 第二十一讲 地址映射、差错报告和多播

4.4 第二十二讲 传递、转发和路由选择

第五章 传输层

5.1 第二十三讲 UDP、TCP和SCTP

5.2 第二十四讲 拥塞控制和服务质量

计算机通信与网络课程总复习知识点

第一部分 概述

第1章 绪论

1、数据通信基本概念及模型
数据通信是在两台设备之间通过诸如线缆的某种形式的传输介质进行的数据交换。
【数据通信系统模型】——五个组成部分

报文:进行通信的信息(数据)
发送方:发送数据报文的设备
接收方:接受报文的设备
传输介质:报文从发送方到接收方之间所经过的物理通路
协议:管理数据通信的一组规则,表示通信设备之间的一组约定

2、数据流:单工、半双工、全双工

单工模式(Simplex Mode):通信是单方向的,两台设备只有一台能够发送,另一台则只能接受
半双工模式(Half-duplex Mode):每台主机均能发送和接受,但不能同时进行
全双工模式(Full-duplex Mode):双方主机都能同时发送和接受

3、连接类型和拓扑结构

点到点连接:提供两台设备之间专用的链路,链路全部的能力均为两台设备之间的传输所共用
多点连接:两台以上设备共享单一链路的情形,通道的能力在空间和时间上共享
拓扑结构:网状、星型、总线、环状

4、网络分类:局域网、城域网、广域网

网络 规模 介质 拓扑结构
局域网LAN 小于2英里 一种类型的传输介质 总线结构、环状结构和星型结构
城域网MAN 十几英里
广域网WAN 世界范围

5、协议和标准
【协议三要素】

语法:指数据的结构或格式,即它们是以何种顺序表示的
语义:指每一位片段的含义:如何解释一个特别的位模式
时序:报文发送的时间和发送的顺序

【TCP/IP】

传输控制协议(TCP)负责高层功能,比如分段、重组和差错控制
网际协议(TP)负责处理数据包路由

第2章 网络模型

1、层次结构、层间接口和封装的概念
【层次结构】:把相关的网络功能组合在一层中,每层都使用其直接下层提供的服务,保持网络灵活且易修改
【层间接口】:数据和网络信息从高层向低层传递和从低层向高层传递都通过相邻两层的接口进行,每一层接口都定义了该层必须向上层提供信息和服务
【封装】:第N-1层的分组中的数据部分是第N层的完整分组(数据、头部、也可能有尾部)
2、OSI参考模型
【开放系统互联(Open System Interconnection)模型】

对等协议:传输层、会话层、表示层、应用层
中间节点只涉及下三层:物理层、数据链路层、网络层

  • 物理层:负责位从一个节点到另一个节点的传递

位的表示:要进行位流的传输必须将位编码成信号——电信号或光信号(物理层定义编码的类型)
数据速率:定义传输速率(每秒发送的位数)
位同步:发送方与接收方不仅使用相同的比特率还必须位同步保证时钟同步
线路配置:点到点连接或多点共享连接
物理拓扑结构:定义设备连接成网络的连接方式(网状、星型、总线、环状)
传输方式:定义两台设备之间的传输方式(单工、半双工和全双工)

  • 数据链路层:负责帧从一跳到下一跳的传递

成帧:数据链路层将接收到的来自网络层的位流分成称为帧的易处理数据单元
物理寻址:1、不同系统 数据链路层在帧的头部添加发送方的物理地址和接收方的物理地址 2、不同网络 数据链路层在帧的头部添加发送方的物理地址和连接下一个网络的路由地址
流量控制:采用流量控制机制防止接收方过载
差错控制:检测与重发损坏帧或丢失帧

  • 网络层:负责将各个分组从源地址传递到目的地址

逻辑寻址:物理寻址负责处理本地网络寻址问题(数据链路层),逻辑寻址负责处理分组通过网络边界的寻址问题
路由选择:在互联网中由连接设备(路由器或网关)负责把分组送到指定网络的目的地

  • 传输层:负责一个报文从一个进程到另一个进程的传递

端口寻址:传输层信息的头部必须包含端口地址(服务点地址),将整个报文传送到计算机上的指定进程
分段和组装:将报文分解成可传输的片段并进行编号,使得1、传输层可以在接收端将报文正确地组装 2、用来标识和替换传输中丢失的分组
连接控制:传输层可以是无连接的或面向连接的
流量控制:负责端到端上的流量控制而不是单条链路
差错控制:负责进程到进程上的差错控制而不是单条链路上

  • 会话层:负责对话控制和同步

对话控制:允许两个进程之间以半双工或全双工方式进行通信
同步:会话层允许一个进程在数据流中增加检查点或同步点

  • 表示层:负责翻译、加密和压缩数据
  • 应用层:负责向用户提供服务

3、TCP/IP协议族
【层次组成】:物理层和数据链路层(主机到网络层)、网络层、传输层和应用层

  • 网络层

    IP协议:不可靠、无连接、主机到主机协议
    组成部分:

    地址解析协议(ARP):将逻辑地址与物理地址联系起来
    逆地址解析协议(RARP):允许主机在仅知道物理地址的情况下寻找因特网地址
    因特网控制报协议(ICMP):用来向发送方通知数据报所发生的问题
    因特网组报文协议(IGMP):用于将一个报文发送给一组接收者

  • 传输层

    用户数据报协议(UDP):进程到进程的协议即端到端的协议
    传输控制协议(TCP):是面向连接的、可靠的流传输协议
    流控制传输协议(SCTP)

4、寻址
【物理(链路)地址(MAC地址)】

用于物理层和数据链路层
以太网中使用6个字节(48位)物理地址,标明在网卡上,长度格式可变

【逻辑(IP)地址】

用于网络层
因特网的逻辑地址是32位地址,唯一地标识了连接到因特网上的一台主机

【端口地址】

用于传输层
赋予进程的标识符称为端口地址,长度固定16位地址

跳到跳时物理地址将改变,但逻辑地址和端口地址保持不变

【专用地址】

用于应用层

第二部分 物理层和介质

第3章 物理层

1、数字信号传输
【电平编码】

信号电平数 $L$,编码电平需要比特位数: $N=\log_2L$
注:通过对多电平编码可以增加每个电平表示的比特位
数字信号是无穷大带宽的复合模拟信号

【基带传输】
$Define:$

通过通道发送数字信号而不转换为模拟信号,即以信号本身的频谱进行传输

只能用带宽下限频率为 $0$ 的低通通道
在基带传输中,所需的带宽与比特率成正比

$Eample\ 1:$

基带传输发送比特率 $n=1Mbps$,求低通通道所需带宽
最小带宽、使用第一谐波 $\Longrightarrow B_1=\frac{n}{2}=500KHz$
使用第一、三谐波 $\Longrightarrow B_3=3\times B_1=1.5MHz$
使用第一、三、五谐波 $\Longrightarrow B_5=5\times B_1=2.5MHz$
$Eample\ 2:$
一条带宽 $B=100kHz$ 的低通通道,求最大比特率
使用第一谐波得到最大比特率 $\Longrightarrow n = 2\times B=200kbps$

【宽带传输】
$Define:$

宽带传输或调制把数字信号转换成模拟信号进行传输

调制允许使用带通通道,即带宽不从0开始的通道
发送模拟信号用带通通道

2、典型的传输减损
【衰减】
$Define:$

通过某种介质传输时,信号能量下降;分贝表示信号损失或增益强度
$dB=10\log_{10}\frac{P_2}{P_1}$
其中,$P_1$、$P_2$ 表示信号前后的功率

【失真】
$Define:$

不同信号成分具有不同的传播速度导致信号波形失真

【噪声】
$Define:$

外界干扰,电缆中的电子随机移动而产生的额外信号

【信噪比】
$Define:$

信号功率与噪声功率的比率
$SNR = \frac{P_1}{P_2}$
其中,$P_1$、$P_2$ 表示平均信号功率和平均噪声功率
分贝单位$\Longrightarrow SNR_dB = 10\log_{10}SNR$

3、数据速率限制
【尼奎斯特定理】——无噪声通道

$S = 2B$
注:有限带宽 $B$ 下,通道的极限波特率(码元速率)为 $2B$

【奈奎斯特速率】——无噪声通道

$N = 2\times B\times log_2L$
注:定义了给定带宽下理论上的最大比特率

【香农容量定理】——有噪声通道

$C = B\times \log_2(1+SNR)$
其中通道容量是指通道的传输容量,即每秒的比特数等于比特率

注:确定噪声通道理论上的最高数据速率

当 $SNR$ 较大时,$SNR+1\approx SNR$,则 $C = B\times \frac{SNR_{dB}}{3}$

$Eample:$
一通道带宽 $B=1MHz$,信噪比 $SNR=63$,求合适的比特率以及信号电平
解:由香农公式确定比特率上限:

$$
C = B\log_2(1+SNR)=6Mbps
$$

为了获得更好的性能,取通道比特率 $N=4Mbps$
由奈奎斯特公式计算信号电平数:

$$
N = 2B\log_2L\rightarrow L=4
$$

香农容量定理给出数据速率的上限,奈奎斯特公式给出所需的信号电平数

4、性能
【带宽】——链路的潜在衡量值,链路最大的数据传输速率
【吞吐量】——发送速度快慢的实际衡量值,小于带宽
【延迟】——第一个位开始发出到整个报文完全到达目标所经历的时间

延迟=传播时间+传输时间+排队时间+处理延迟

传播时间——一个位从源传输到目标所需时间(与介质相关)

$$
Tp = \frac{d}{v}
$$

传输时间——传输一个报文的时间

$$
Tt = \frac{LF}{B}
$$

其中,帧长 $LF$ 表示一个报文长度

排队时间——每个中间或端设备在处理报文前保持报文所需的时间

【带宽与延迟乘积】——定义了能充满链路的位数(通常用的是传播时延)

第4章 数字传输

1、线路编码——将数字数据(比特位)转换为数字信号(高低电平)的过程
【数据元素】表示一块信息的最小实体即位
【信号元素】承载数据单元,是数字信号的最小单元
$Define:$

承载比率 $r$: 每个信号元素承载的数据元素的数量
$$ r = \log_2L $$

【数据速率(比特率)】表示1秒发送的数据元素(位)的数量(单位:bps)
【信号速率(波特率)】表示1秒发送的信号元素的数量(单位:波特baud)
比特率和波特率关系:

$$
S = c\times N\times \frac{1}{r}\ \ baud
$$

其中,$N$ 表示比特率,$S$ 表示波特率,$c$ 表示情形因子(一般取 $0.5$),$r$ 表示承载比率

波特率决定了数字信号的带宽,并且带宽与波特率成正比

【最小带宽】

$$
B_{min}=c\times N\times \frac{1}{r}
$$

最小带宽$B_{min}$与波特率相等(至少保证能够传输信号)

当通道带宽为 $B$ 时,得出最大数据速率:

$B_{min}=c\times N\times\frac{1}{r}\leq B\rightarrow N\leq \frac{1}{c}\times B\times r$
$\Longrightarrow N_{max}=\frac{1}{c}\times B\times r$
注:$B_{min}$ 表示信号所需最小带宽,$B$ 表示通道带宽

【直流分量】——信号电平保持一段时间的恒定,使得频谱中对应的频率很低称为 DC(直流)分量
【自同步】——接收方的位间隔必须与发送方的位间隔一致

数字信号在传输的数据中包含有定时信息:提示接收方起始、中间和结束位置的脉冲的跳变

2、线路编码方案
不同编码方案平均带宽计算:

$B_{min}=S = c\times N\times\frac{1}{r}$
$c=0.5\Longrightarrow B_{min} = \frac{N}{2r}$
正电平定义成位 $1$ 而零电平定义成位 $0$,位中间信号不会回到 $0$
$r=1$,平均带宽 $B = \frac{N}{2}$
成本高,$0$ 或 $1$ 的长序列没有自同步,存在 $DC$ 问题
$RZ+NRZ-L$
使用正值、负值两个电平,正电平定义成位 $0$,负电平定义成位 $1$,位中间跳变成另一电平 $\Rightarrow$ 解决同步问题

3、块编码:4B/5B、8B/10B(了解)
4、扰码
【B8ZS】——8零置换的双极编码方案

$$
B8ZS:00000000\Rightarrow 000VB0VB
$$

其中,$V$ 表示与前一个非零脉冲极性相同的极性,$B$ 表示与前一个非零脉冲极性相反的极性

5、脉冲码调制PCM
【采样】——方顶采样
模拟信号采样周期$T_S$,采样频率$f_S=\frac{1}{T_S}$
根据奈奎斯定理,采样速率必须至少是信号所含最高频率的 $2$ 倍:

$$
f_S\geq 2f_m
$$

【量化】

  • 将最低振幅 $V_{min}$ 和最高振幅 $V_{max}$ 范围量化为 $L$ 个区间
  • 区间高度:$\Delta = \frac{V_{max}-V_{min}}{L}$
  • 标准化 $PAM$ 值/振幅= 实际振幅/$\Delta$
  • 标准化量化值=样本所在区间的中间量化值(单位为 $\Delta$)
  • 量化误差=标准化量化值-标准化振幅值,一般 $-\frac{\Delta}{2}\leq$ 误差 $\leq\frac{\Delta}{2}$
  • 量化码:$0\thicksim7$ 编码对应 $-4\Delta\thicksim 4\Delta$ 每一个区间
  • 编码码字:$0\thicksim7\Longrightarrow 000\thicksim111$

【量化等级】——取决于模拟信号的振幅范围
【量化误差】
对信号 $SNR_{dB}$ 的影响:

$$
SNR_{dB}=6.02n_b+1.76dB
$$

其中,$n_b$ 表示每个样本的编码位数,$n_b=log_2L$ ($L$ 表示量化等级数即电平数)

【PCM数字化模拟信号的比特率和带宽】

$f_S=2f_m$
$\Rightarrow N = f_S\times n_b =2f_m\times\log_2L$
$B_{min}=c\times N\times\frac{1}{r}$
$=c\times f_S\times n_b\times \frac{1}{r}$
$=c\times 2\times B_{analog}\times n_b\times \frac{1}{r}$
$=n_b\times B_{analog}$
其中,$B_{analog}$ 表示低通模拟信号的带宽即信号最高频率

6、Delta调制 (DM)的概念
【调制】

数字数据生成:将模拟信号的值与梯形信号的最后一个值比较,如果模拟信号的振幅大,则数字数据下一个位为 $1$,否则为 $0$;
梯形信号生成:如果数字数据下一位为 $1$,则梯形信号的最后一个点上移 $\delta$,否则下移 $\delta$;

7、传输模式
【并行传输】

使用 $n$ 个通信线路同时发送n位
优点:速度快,用于短距离通信
缺点:成本高

【串行传输】

包括异步和同步传输
优点:成本低,适合远距离通信
缺点:速度慢

【异步传输】

在传输中信号的时序并不重要
信息的接受和转换通过约定的模式进行
字节级异步:将位流组成字节(通常是 $8$ 位)的方式进行分组发送
字节内同步:没有同步时钟,每个字节增加起始位和停止位,并且每个字节之间有一个时间间隔

【同步传输】

位流被组合成更长的帧,一帧包含多个字节,按序发送
依次发送位流而不含起始位、停止位和间隙,接收方负责将位进行分组
帧间可能有不等的时间间隔,常用于大块二进制数据传送

同步传输比异步传输速度快

第5章 模拟传输

1、比特率和波特率
$Define:$
$$
r = log_2L\newline
S=N\times\frac{1}{r}
$$
其中,$L$ 表示不同类型的信号元素个数(数字传输中 $L$ 为电平个数)

2、数字到模拟转换的概念

数字数据转换为带通模拟信号 $\Rightarrow$ 数字到模拟转换
低通模拟信号转换为带通模拟信号 $\Rightarrow$ 模拟到模拟转换

【幅移键控((B)ASK)】

通过改变载波信号的振幅来生成信号元素,只有振幅变化而频率和相位保持不变

【带宽】

$B=(1+d)\times S$
$S = N\times \frac{1}{r}\Rightarrow B = (1+d)\times N\times\frac{1}{r}$ 反推 $N$

【频移键控((B)FSK)】

通过改变载波信号的频率来生成信号元素,只有频率变化而振幅和相位保持不变

【带宽】

$$
B=(1+d)\times S+2\Delta f
$$

其中,$\Delta f$ 表示两个信号元素的频率差

【相移键控(PSK)】

通过改变载波信号的相位来生成信号元素,只有相位变化而振幅和频率保持不变
BPSK:二进制PSK,只用两个信号元素,一个相位是$0$ 度,另一个相位是 $180$ 度
QPSK:正交PSK,使用两个独立的BPSK调制,一个是同向的,另一个是正交的

QPSK中相位可能是 $45$ 度,$-45$ 度,$135$ 度和 $-135$度之一,输出信号有 $4$ 种信号元素,每个信号元素可以承载 $2$ 位
【带宽】

$B=(1+d)\times S=(1+d)\times N\times\frac{1}{r}$
$BPSK:\ r=1\Longrightarrow B = (1+d)\times N$
$QPSK:\ r=2\Longrightarrow B = (1+d)\times \frac{N}{2}$

【正交振幅调制(QAM)】

ASK+PSK:使用两个载波,一个同向而另一个正交,每个载波都用不同的振幅

【n-QAM带宽】

$$
r = \log_2n\Rightarrow B = (1+d)\times N\times\frac{1}{r}
$$

第6章 带宽利用

1、复用:FDM、同步TDM、统计TDM和WDM概念
【复用带宽要求】
连接两台设备的介质带宽要比设备间传输所要求的带宽高
【频分复用(FDM)】——用于模拟信号

链路带宽(以Hz为单位)大于要传输的信号的带宽之和
将链路带宽进行分频给每个信号通道,通道间存在未使用的带宽即防护频带

【波分复用(WDM)】

用于具有高数据速率传输能力的光缆,是合并多个光信号的模拟多路复用技术

【时分复用(TDM)】

TDM在时间上共享,每个连接占用链路的一个时间段,是组合多个低速的通道为一个高速通道数据的复用技术

【同步TDM】

每个输出单元的持续时间是输入单元的$n$ 分之一,其中 $n$ 表示连接数
链路速率是数据速率的$n$ 倍,并且比单元持续时间短 $n$ 倍
帧同步,每帧开始增加一位帧指示位,交替变换为 $0$ 和 $1$

【同步TDM数据速率管理】
各数据线数据速率不相等时处理技术:

处理策略 使用情况 特点
多级复用 一条输入数据线数据速率是其他一些输入数据线数据速率的整倍数 合并低数据速率通道,$m\times n$,$m$表示连接数
多时隙复用 在一个帧中允许对一条输入分配多个时隙 分离高数据速率通道,$\frac{n}{m}$,$m$表示分配的连接数
脉冲填充 输入线的比特率不是其他每个输入线比特率的整数倍 低速率的输入线添加虚位

【统计TDM】——动态分配时隙,提高链路利用率

输出时隙必须携带数据和目的地址(目的地址+数据)
$N$ 条输出线编码表示: $$ n=\log_2N $$
无同步位,存在通道寻址因此不需要同步位
链路容量小于各通道之和

【脉冲调制PCM体制两大国际标准】

服务 $DS-1$ 线路 $T-1$
速率:$1.544Mbps$
用途:传输音/视频,也可用于模拟传输
语音通道:$24$ 个
时分多路复用技术(TDM)
$DS-1$ 需要 $8kbps$ 开销
我国采用的是欧洲的E1标准

3、波分和码分的概念
4、FHSS和DSSS的概念

第7章 传输介质

1、有向介质:双绞线及其特点、同轴电缆和光纤的概念
2、无线传输介质:无线波谱、无线电波、微波和红外波

第8章 交换(传输时延分析)

1、电路交换网络——效率低、延迟最小
电路交换网络是由物理链路连接的一组交换机组成的,每条链路划分成 $n$ 个通道,两个站点的连接是由一条或多条链路组成的专用路径来实现

电路交换在物理层
资源预留:通信开始前,站点需要对通信所用的资源进行预留
连续数据流:数据传输不打包
数据传输期间无寻址

【建立阶段】——每条链路上预定一个通道,联合起来指定一条专用路径

建立阶段进行资源预留、端到端寻址

【网络延迟】

延迟时间=建立连接时间+数据传输时间+拆除电路时间
建立连接时间=请求信号传播+请求信号传输时间+确认信号传播时间+确认信号传输时间
数据传输时间=数据传播时间+数据传输时间

2、分组交换网

数据报网络
虚电路网络

分组交换网中,不存在资源预留,资源按需分配

3、数据报网络——效率较高,延迟较长

每个分组独立处理,数据报交换在网络层
不需要建立连接阶段和拆除阶段
每个分组头部包含目的地址,且在分组传送期间保持不变(物理地址会变)

数据报网中的交换机使用基于目的地址的路由表

【网络延迟】

延迟时间=传输时间+传播时间+等待时间
$Example:$ 分组通过两个交换机传送分析:
总延迟时间 $=3\times$ 传输时间 $+3\times$ 传播时间 $+$ 在交换机 $1$ 处等待时间 $+$ 在交换机 $2$ 处等待时间
因特网在网络层用数据报方法对数据进行交换

4、虚电路网络——

电路交换+数据报网络
虚电路网络在数据链路层实现
在数据传输阶段,存在建立阶段与拆除阶段
按需在建立阶段期间分配资源
每一分组头部含有目的地址,具有本地权限而非端到端权限(定义下一个交换机和分组的通道地址,虚电路标识符实现)
所有分组沿着建立的路径进行传送

【虚电路标识符(VCI)】
一个VCI仅是在交换机范围内的小数字,由两个交换机之间的帧来使用,通过交换机时更新VCI
【虚电路网络表】

表项构成:输入端口,输入VCI,输出端口,输出VCI

【网络延迟】

延迟时间=传输时间+传播时间+建立阶段延迟+拆除阶段延迟
$Example:$ 分组通过两个交换机传送分析:
总延迟时间 $=3\times$ 传输时间 $+3\times$ 传播时间 $+$ 建立阶段延迟 $+$ 拆除阶段延迟

第三部分 数据链路层

第10章 检错与纠错

1、差错的类型
【单个位差错】——数据单元仅有一位发生变化
【突发性差错】——数据单元有两位或多位发生变化
2、块编码

报文划分成块,每个块有k位——数据字
数据字+r个冗余位形成长度n=k+r的块——码字

数据字: $2^k$ 码字: $2^n$
$\Longrightarrow$ 非法码: $2^n-2^k\ (n>k)$

3、纠错方法
【汉明距离】——两个相同长度的字的汉明距离是对应位不同的数量

$$
10101\oplus 11110=01011\Rightarrow d(10101, 11110)=3
$$

【最小汉明距离】——一组字中所有可能对中的最小汉明距离

$d_{min} = \min${两两间的汉明距离}
为了检测出所有情况下最多$s$个差错,块编码中最小汉明距离一定是$d_{min}=s+1$
为了纠正所有情况下最多$t$个差错,块编码中最小汉明距离一定是$d_{min}=2t+1$

4、线性块编码
【线性块编码最小距离】——最小汉明距离

最小汉明距离是具有最少1的个数的非$0$ 有效码字中 $1$ 的个数
注:每个非零码字中,具有最少$1$ 的码字对应 $1$ 的个数

【简单奇偶校检码】

校检编码$n=k+1、d_{min}=2$,单个位或奇数个位检错编码,不能纠错

【二维奇偶校检码】——最多能检测 $3$ 个差错
【汉明编码】

$n=2^m-1,\ \ k=n-m$
$\Longrightarrow$ 校检位个数: $r=m$
$d_{min}=3\Rightarrow$ 校检 $2$ 位,纠正 $1$ 位

编码分析

$a_3a_2a_1a_0r_2r_1r_0\Longrightarrow b_3b_2b_1b_0q_2q_1q_0$
奇偶校检位:
$r_0=a_2+a_1+a_0$
$r_1=a_3+a_2+a_1$
$r_2=a_3+a_1+a_0$
奇偶校检方程:
$s_0=b_2+b_1+b_0+q_0$
$s_1=b_3+b_2+b_1+q_1$
$s_2=b_3+b_1+b_0+q_2$
校正子 $s_2s_1s_0$ 出错位
6 110 $b_3$
3 011 $b_2$
7 111 $b_1$
5 101 $b_0$

5、循环冗余编码校检码(CRC码)

数据字:$k$位,码字:$n$位,校检位:$n-k$位,除数:$n-k+1$位,余数:$n-k$位

编码分析

余数=(数据字+($n-k$)位 $0$) $\%$ 除数 (模 $2$ 除法)
$\Longrightarrow$ 校检位=余数
$\Longrightarrow$ 码字=数据字+校检位
校检:
校正子=码字$\%$除数
if 校正子== $0$: 接受数据字 else 丢弃数据字
检错类型 (除数)生成多项式$g(x)$
捕捉单个位差错 $g(x)$至少有两项并且$x^0$的系数为1
两个独立的单个位差错 $g(x)$不能整除$x^t+1(t\in [0,n-1], t\in Z)$
奇数个差错 $g(x)$有因式$x+1$
突发性差错 所有$L\leq r$的差错均可被检测;$L=r+1$的差错被检测概率$P=1-{\frac{1}{2}}^{r-1}$;$L>r+1$的差错被检测概率$P=1-{\frac{1}{2}}^r$;(其中$L$表示差错长度,$r$表示冗余位长度

6、校检和及其计算方法

需要将数据划分为多组的16bits数据
校检和计算

第11章 数据链路控制

1、组帧

在数据链路层,成帧将一条从源端到目的端的报文分离开来,或者将到不同目的端的报文分离开来

【固定长度成帧】——不需要定义帧的边界,长度本身可以用作分隔符
【可变长度成帧】

  • 面向字符协议——帧的开始和结尾加一个字节的标记
    帧格式:标记+头部+可变数量的字符(来自上层的数据)+尾部+标记
    转义字节:$01111101$【PPP协议】
标记冲突解决:字节填充,在字符标记的前面添加一个字节(换义字符ESC)以跳过该字符标记
  • 面向位协议
    帧格式:标记+头部+可变数量的位(来自上层的数据)+尾部+标记
    特定的标记:$01111110$【HDLC协议】
标记冲突解决:位填充,遇到一个$0$ 后面紧跟 $5$ 个 $1$ 便添加一个 $0$
数据链路控制:流量控制+差错控制

2、流量控制与差错控制
【流量控制】——一系列程序,用来限制发送方在等到确认之前发送的数据数量
【差错控制】——基于自动重复请求(ARQ)进行差错检测和重传
【ARQ】
ARQ技术就是自动请求重发技术,结合了流控和自动重发技术,该技术的主要思想是利用差错检测技术自动对丢失的帧和错误帧请求重发

3、停止等待ARQ——有噪声通道

差错检测由保留已发送帧的副本并当计时器到时重传这个帧来实现
使用序列号给帧编号,该序列号基于模 $2$ 运算
确认号总是以模2运算宣布期待收到下一帧的编号

【链路利用率】

带宽 $B$,一个位往返时间:$t$,数据帧的长度:$L$
$\Longrightarrow$ 带宽延迟乘积=$B\times t$
$\Longrightarrow$ 链路利用率 = $L$/带宽延迟乘积

4、后退N帧ARQ——有噪声通道

序列号是模 $2^m$,$m$ 表示以位为单位的序列号字段长度
一个ACK可以确认一个以上的帧

【协议原理】

  • 后退 $N$ 帧ARQ协议就是从出错处重发已发过的 $N$ 个帧;
  • 在后退 $N$ 帧协议中,发送方按照窗口中帧的编号顺序连续发送帧,接收方窗口大小总是 $1$;
  • 接收方只能按顺序接受,并按顺序发送应答信号;
  • 对于没有按顺序达到的帧丢弃,以后要重新发送
发送方窗口大小$2^m-1$ (一定要小于 $2^m$),接收方窗口大小为 $1$
后退N帧ARQ窗口变化

5、选择重发ARQ——有噪声通道

发送方窗口大小 $\leq2^{m-1}$,接收方窗口大小与发送方一致

选择重发ARQ

6、高级数据链路控制(HDLC)

面向比特的点到点和多点链路进行通信的协议

【正常响应方式】
【异步平衡方式】
【定义帧】

  • 信息帧
  • 管理帧
  • 无编号帧

7、点到点(PPP)协议——面向字节的方式

第12章 多路访问

1、随机访问
【纯ALOHA】——每个站点有帧要发送,就发送帧

  • 脆弱时间: $2\times T_{fr}$
  • 吞吐量: $S = G\times e^{-2G}$
    当 $G=\frac{1}{2}$ 时,则 $S_{max}=0.184$
    其中,$G$ 表示一个帧传输时间内系统产生的帧的平均数量

【时隙ALOHA】——强制站点只有在时隙开始之时才能进行发送

  • 脆弱时间: $T_{fr}$
  • 吞吐量: $S = G\times e^{-G}$
    当 $G=1$ 时,则 $S_{max}=0.184$
    其中,$G$ 表示一个帧传输时间内系统产生的帧的平均数量

【载波侦听多路访问CSMA】——传输前先侦听

  • 脆弱时间=传播时间: $T_{p}$
  • 吞吐量: $S = G\times e^{-G}$
    当 $G=1$ 时,则 $S_{max}=0.184$
    其中,$G$ 表示一个帧传输时间内系统产生的帧的平均数量
  • 持续方法:1-持续、非持续、p-持续

【带冲突检测的载波侦听多路访问CSMA/CD】——边发边听
$Example:$ CMSA/CD网络,带宽 $B=10Mbps$,最大传播时间 $T_{p}=25.6\mu s$,求帧的最小长度
解:帧的传输时间 $T_{fr}=2\times T_{p}=51.2\mu s\ (T_{fr}\geq T_{p})$
帧的最小长度$=B\times T_{fr}=B\times 2T_{p}=512\ bits$

【带冲突避免的载波侦听多路访问CSMA/CA】

  • 三种方法:帧间间隔、竞争窗口、确认

2、受控访问

  • 预约
  • 轮询
  • 令牌环

3、通道化:FDMA、TDMA、CDMA

第13章 有线局域网:以太网

1、IEEE标准

数据链路层划分为两个子层:逻辑链路控制层(LLC)和介质访问控制层(MAC)

2、标准以太网的MAC子层
【帧格式】——最小长度 $64$ 字节
【MAC地址】

源地址一定是单播地址
$6$ 字节 = $12$ 十六进制数字 = $48$位

第一个字节的最低位为0则地址是单播地址否则是多播地址
广播地址是多播地址的一个特例,所有位(48位)都是1

【编码和解码】

标准以太网中实现的编码是曼彻斯特编码
IEEE 802.5中实现的编码是差分曼彻斯特编码

【$10$Base$5$】

传输速度 $10Mbps$,基带传输,传输最大距离 $500$ 米
粗缆以太网
半双工

【$10$Base$2$】

传输速度 $10Mbps$,基带传输,传输最大距离 $200$ 米
细缆以太网
半双工

【$10$Base-T】

传输速度 $10Mbps$,基带传输,双绞线
最大长度:$100$米
双绞线以太网
全双工

【$10$Base-F】

传输速度 $10Mbps$,基带传输,光纤
最大长度:$2000$ 米
光纤以太网
全双工

【桥接以太网】

存在网桥——作用:提高带宽和分割冲突域

【交换式以太网】

存在交换机

【全双工以太网】

站点和交换机之间使用两条链路

3、快速以太网、千兆以太网

第14章 无线局域网

1、IEEE $802.11$ 标准——涵盖物理层和数据链路层
【基本服务集(BSS)】

服务点AP:中央基站

不带AP的BSS称为特别网络,带AP的BSS称为基础网络

【扩展服务集(ESS)】

由两个或多个带有AP的BSS组成
各个BSS通过一个分布式系统(通常是有线局域网)连接BSS中的AP而组合起来

2、$802.11$ MAC子层(DCF和PCF)
【分布式协调功能DCF】

访问方式:CSMA/CA
需要竞争使用信道

【点协调功能PCF】

集中式的、无竞争的轮询访问方式
PCF的优先级高于DCF

【帧格式】

  • 帧控制(FC)——$2$ 字节
  • D——$2$ 字节
  • 地址——有四个地址字段,每个 $6$ 字节
  • 序列控制——$2$ 字节,用于流量控制
  • 帧主体——$0\sim2312$ 字节
  • FCS——$4$字节,CRC-$32$的差错检测序列

【帧类型】
IEEE $802.11$ 定义帧类型:管理帧、控制帧和数据帧
3、隐藏站点和暴露站点
【隐藏站点】——B和C对于A来说是相互隐藏的

CSMA/CA握手中的CTS帧可以避免来自隐藏站点的冲突

【暴露站点】——站点被限制使用通道,而这个通道是可用的

第15章 连接局域网、主干网和虚拟局域网

1、连接设备
【无源集线器】——工作在物理层以下

集线器是冲突点

【中继器】——工作在物理层

中继器连接一个局域网的各个网段,因此不能连接两个不同协议的局域网
中继器转发每一帧,没有过滤能力
是再生器,重新生成信号,不是放大器

【有源集线器(hub)】——工作在物理层

所有的端口是一个广播域,也是一个冲突域

【网桥】——工作在物理层和数据链路层

所有的端口是一个广播域,每个端口是一个冲突域(需要竞争使用)
网桥具有过滤能力,有一个过滤决策的表
可靠性高:网络故障只影响其所在的网段
不改变帧中所包含的物理地址
连接局域网

【透明网桥】

是一个它所连接的站点完全意识不到其存在的网桥

【生成树】

从网桥到LAN的跳数为 $1$,而从LAN到网桥的跳数为 $0$

  • 选择 $ID$ 最小的网桥作为根网桥
  • 找到从根网桥到其他每个网桥或LAN的最短路径
  • 最短路径的组合生成了最短的树

转发端口:属于生成树部分的端口
阻塞端口:不属于生成树部分的端口

【两层交换机】——工作在物理层和数据链路层

没有通信量的竞争
对帧的MAC地址具有过滤决策
所有端口是一个广播域,每个端口是一个冲突域

【路由器】——工作在物理层、数据链路层和网络层

在硬件上实现了路由器的分组转发逻辑
基于分组的逻辑地址进行路由转发
每个端口是一个广播域也是一个冲突域

【三层交换机】——工作在物理层、数据链路层和网络层

每个端口是一个广播域也是一个冲突域

【网关】——工作在所有五层或OSI模型全部七层

不仅仅包含路由、交换功能,还包括应用级的功能

2、虚拟局域网

虚拟局域网: 通过软件而非物理线路来配置的局域网

【站点分组的依据】——端口号、MAC地址、IP地址、多播IP地址、联合使用

第18章 虚电路网络:帧中继和ATM

1、【帧中继特点】——虚电路广域网

  • 速率较高
  • 允许突发性数据
  • 花费少
  • 工作在物理层和数据链路层
  • 仅在数据链路层有错误检测,没有流量和错误控制
帧中继不提供流量和差错控制,这些必须由上层协议提供
帧中继提供拥塞控制和服务质量

【帧中继的结构】

  • 帧中继是一种虚电路网络,虚电路用数据链路连接标识符(DLCI)定义
  • 帧中继中的VCI(虚电路标识符)称为DLCI

2、异步传输模式(ATM)——信元交换网路

信元中继协议
传输的数据单元:信元(长度不变)
使用异步时分复用技术处理来自不同通道的信元
具有先进的拥塞控制和服务质量
需要建立虚电路进行通信

信元网络使用信元作为数据交换的基本单位,信元定义为一个小的、固定大小的信息块($53$B=$5$B头部+$48$B数据)

【传输路径(TP)、虚路径(VP)和虚电路(VC)】

  • 传输路径是一个端点与一个交换机或者两个交换机之间的物理连接
  • 虚路径提供两个交换机之间的一条连接或连接的集合
  • 虚电路是属于同一报文的所有信元沿着同一虚电路传输,同时保持原始次序

【虚路径标识符(VPI)、虚电路标识符(VCI)】

VPI定义特定的VP,VCI定义特定的VC

一个虚连接由一对数字定义:VPI、VCI,其包含在信元的头部

第四部分 网络层

第19章 逻辑寻址

1、IPv4地址分类,掩码,子网和超网的概念

IPv4地址划分
类别 可指派网络号范围 可指派的网络数 可分配的IP地址数
A 0000 0001— 1111 1110 2^7 -2 2^24 -2
B 128.0—191.255 2^24 2^16 -2
C 192.0.0—223.255.255 2^21 2^8-2
D 多播地址
E 保留

【子网掩码】

将IP地址的主机号部分借用几位作为子网号以区分同一网络下的不同网络(子网)

【超网】

超网(CIDR)消除了传统的A类、B类和C类地址以及划分子网的概念,将网络前缀相同的IP地址组成一个地址块

记法:IP地址 + “/” (斜线后写上网络前缀所占的比特数量)

2、子网划分方法、子网范围计算

  1. 子网掩码用连续 $1$ 表示对应的网络号和子网号;连续 $0$ 表示主机号
  2. 将IPv4地址与子网掩码“相与”,即可得到所在子网的网络地址

由子网掩码说明只借用了主机号一位,所以共划分出两个子网,每个子网可分配的地址数为:

$$
2^7-2
$$

3、NAT

为了解决地址短缺,内部可有大量地址,对外通信采用的一个外部格式;能使得大量使用内部专用地址的用户共享外部的全球地址,以访问因特网主机资源

4、IPv6地址及其缩短形式
IPv6地址

第20章 IP协议

1、IP数据报的格式

固定首部+数据载荷

2、分片与MTU

【MTU】

最大传送单元 : MTU 是链路层可封装数据 的上限

【分片】

更多操作 IP 分组的 MTU 是 1500 字节 , 当网络层的 IP 分组超过 1500 字节 , 此时就要进行分片,将数据报分割,使其能通过不同的网络

根据首部的标识 , 标志 , 片偏移(必须为整数) 进行相应处理

3、IPv4校验和

更多操作将校验和置$0$,以 $16$bit为一组求校验和

4、IPv6分组格式

基本头部固定为$40$B,有效载荷 $Max=65536$B

5、IPv4和IPv6混合

  1. 隧道技术:两台使用IPv6电脑的报文通过IPv4区域时,IPv6分组封装成IPv4的技术
  2. 头部转换:发送方用IPv6,接收方用IPv4,则IPv6头部应该转换为IPv4

第21章 地址映射、差错报告和多播

1、APR

概念

逻辑地址映射到物理地址, ARP Address Resolution Protocol)

过程

2、DHCP的概念

可以提供静态/动态/自动/人工的地址配置

3、ICMP

概念作用

差错报告

ICMP差错报文总是将报文传递给源方

4、IGMP

IGMP是组管理协议,它为多播路由器提供有关连接到该网络上成员的相关信息

第22章 传递、转发和路由协议

1、转发技术与转发过程

转发是指将分组路由到它的目的端
  • 下一跳方法:路由表只保留下一跳地址
  • 路由方法:保留完整路由信息
  • 特定主机/特定网络方法

2、路由表、地址聚合和最长掩码匹配

3、单播路由协议

【RIP】:以距离向量衡量,用于应用层

【OSPF】:以链路状态衡量,用于传输层

【BGP】:以路径向量衡量,用于应用层

4、多播的概念和多播路由协议(了解)

第五部分 传输层

第23章 传输层三种协议:UDP、TCP和SCTP

1、端口(重要端口)、套接字

层结构 传输地址
数据链路层 MAC地址
网络层 IP地址
传输层 端口地址

端口号:$16$bits$\Rightarrow 0\thicksim 65535$
端口划分:

  • 熟知端口: $0\thicksim 1023$
  • 注册端口: $1024\thicksim 49151$(防止端口被重用)
  • 动态端口(临时端口): $49152\thicksim 65535$(可随意使用)
套接字地址:IP地址+端口号

2、UDP协议

用户数据报协议(UDP)
无连接服务、不可靠、无流量控制和差错控制

【数据报结构】

UDP分组称为用户数据报,有8字节的固定头部
固定头部:源端口号、目的端口号、长度(定义数据报总长度)、校检和
UDP被封装成IP数据报:伪头部是IP分组的头部一部分,而头部是UDP的一部分
数据(必须进行填充是数据是16位的倍数)

UDP长度=IP长度-IP头部长度

【校检和的计算】——针对UDP的头部加上去除填充的数据

每两个字节模2求和,最后结果取反得到校检和

3、TCP协议

传输控制协议(TCP)
全双工、面向连接、可靠的、提供流量控制和差错控制
建立虚拟连接,逻辑上的连接
TCP允许发送进程以字节流的形式传递数据,并设置有发送和接受缓冲区
TCP将多个字节组合在一起成为一个分组,称为段
段的头部包含有序号、确认号两个字段(序号指字节序号开始于一个随机数编号而非段序号)
段序号指该段的第一个字节的序号,段中确认字段定义了接收方预期接受的下一字节的编号

【连接建立(三次握手)】——SYN表示序列同步号

  • 客户发送第一个段SYN段,用于序列号同步,不携带数据但占用一个序列号
  • 服务器发送第二个段,SYN+ACK段,SYN表示另一方向通信的SYN段(全双工),ACK表示对第一个SYN的确认,不携带数据但占用一个序列号
  • 客户发送第三个段,ACK段进行确认,不携带数据也不占用序列号

【终止连接(三次握手)】——将SYN换做FIN
【流量控制】——信贷滑窗协议

面向字节的、窗口大小可变
窗口的张开、合拢和收缩由接收方控制

窗口大小=$\min(rwnd,cwnd)$

【差错控制】——校检和、确认和重传

  • ACK段不占用序列号,不需要确认
  • 超时重传:重传计时器到时,快速重传:发送方接收到三个重复的ACK
  • 数据可以失序到达,并被接受的TCP暂时存储,但是TCP确保传递给进程的段是无失序的

第24章 拥塞控制和服务质量

1、TCP拥塞控制
【慢启动过程】

每次接收到一个确认时,窗口大小增加一个MSS值
以 $2$ 的幂次增加,单位是MSS值

在慢启动算法中,拥塞窗口大小按指数规律增长直到达到阈值

【拥塞避免:加性增加】

当拥塞窗口达到慢速启动的阈值时,慢速启动阶段停止,加性增加阶段开始
每次整个窗口所有段都被确认时,拥塞窗口才增加 $1$

拥塞避免算法中,拥塞窗口大小加性增加直到检测到拥塞

【拥塞检测:乘性减少】

发生拥塞时,拥塞窗口阈值下降一半

如果计时器到时,开始一个新的慢速启动阶段
如果检测出三个ACK,开始一个新的拥塞避免阶段

2、服务质量
【概念】数据流所追求的某种目标

第六部分 应用层

第25章 域名系统

1、域名空间DNS
【域名树】——最多有 $128$ 级,$0$ 级根节点,节点标号为字符串,根节点标号为空串

从下向上读,最后一个字符为 $’.’$
全称域名:以空字符串结束,最后一个字符是 $’.’$
部分域名:起始于一个节点,但未到根节点

2、域名空间三个部分:反向域、通用域和国家域
【通用域】按照已经注册的主机的一般行为对主机进行定义

com edu gov info int mil org pro
【国家域】
cn us

【反向域】用于将地址映射为名字
3、域名解析
【递归解析】
将客户机的请求不断传递给父服务器并等待响应,查询得到解析后响应后向传送直到最终到达发出请求的客户机
【迭代解析】
服务器或者发送应答,或者返回另一个服务器的IP地址,由客户机负责再次发送请求
4、DNS报文
【查询报文】——头部+查询记录
【响应报文】——头部+查询记录+响应记录+授权部分+附加部分
5、URL
访问Web的主机统一命名:协议://主机://端口://路径

Contributors

Zhihao Li, Computer Science and Technology, Xidian University

https://zhihaoli.top

Jiawei Hu, Computer Science and Technology, Xidian University

https://jiaweihu-xdu.github.io/

References

Behrouz, a.forouzan. (n.d.). 数据通信与网络 (原书第 4 版)

http://m.cmpedu.com/books/book/2011466.htm

杨力. 2023年春, 计算机通信与网络, 西安电子科技大学.

https://mooc1.chaoxing.com/mooc-ans/course/231806185.html

Author

Zhihao Li

Posted on

2023-09-13

Updated on

2024-12-25

Licensed under


Comments