0x00 基本功能

功能：

为网络层提供服务
- 无确认的无连接：适用于实时通信，如以太网
- 有确认的无连接：适用于误码率较高的场合，如无线通信
- 有确认的面向连接的：适用于可靠性实时性较高的场合
- 就是没有无确认的有连接
链路管理：链路建立、维持和释放
组帧
- 定义帧的数据格式
- 帧定界：确定帧的界限，添加首部和尾部，用标志位F（0111 1110）
- 帧同步：发送方和接收方都能区分出帧的起始和终止
透明传输：保证任何数据都能在链路上传输
流量控制：实际上限制发送方的数据流量，以防接收方跟不上
差错控制

进一步说一下何谓可靠服务何谓不可靠服务：

可靠服务由网络本身负责，通过一系列的机制来保证传输的可靠性，可靠服务通过检错、纠错、应答机制来保证数据最后准确地到达目的地，对于不可靠的服务，则必须通过应用或用户来保障数据传输的正确性

0x01 组帧

字符计数法：在头部加一个字段来标识帧内的字符数，知道这个数即可确定帧的结束位置，最大的问题在于，如果这个数出错将会带来灾难性后果。
字符填充的首尾定界符法：在头部和尾部加一些特定的字符来标识开始和结尾，信息位中如果有相同的字符，就使用转义字符将其转义
比特填充的首尾标志法：用0111 1110作为首尾的界限，如果数据段中每出现5个1就在后面加个0
违规编码法：局域网使用的就是这种方法，例如在曼彻斯特编码中就没有出现高-高这样的电平对，所以就用这种违规编码来标识帧的首尾

0x02 差错控制

差错的引发：

随机热噪声：信道所固有的，持续存在的，引起的差错为随机差错，通过提高信噪比可以减少其对数据传输的影响
冲击噪声：是引起传输差错的主要原因

差错控制：

自动重传请求（ARQ）：接收端只能检测出差错，然后要求重传
前向纠错（FEC）：不但能发现差错，还能确定差错的位置

检错编码：

奇偶校验码：加一个标志位使其有偶数个1（偶校验）或奇数个1（奇校验），如果采用奇校验，则如果传输的结果中有偶数个1那么可以检测出差错来，如果具有奇数个1则检测不出差错
CRC循环冗余码：可以使用硬件完成，带有r个校检位的多项式编码可以检测到所有长度小于等于r的突发性错误。

$\text{CRC的计算} \\ 首先会有一个生成多项式，可能写成G(x)=x^4+x+1或者10011的形式 \\ 最高项的次数即为r，如果是二进制数的形式即为位数-1，上述2例中r=4 \\ \text{CRC的生成}：在发送序列后加入r个0，然后使用模2除法计算余数 \\ 将计算所得的余数附加至发送序列后面即得到\text{CRC序列} \\ \text{CRC的检验}：将发送过来的序列与生成多项式使用使用模2除法计算余数 \\ 若余数为0则该二进制序列在传输过程中没有出现差错$

下图为对发送序列101001使用生成多项式1101（或 $G(x)=x^3+x^2+1$ ）使用模2除法计算余数的过程：

故：所得发送序列为101001 001

纠错编码：

海（汉）明码：能发现双比特错，但只能纠正单比特错，纠错D位，需要码距（海明距）为2d+1的编码方案，检错d位，需要码距为d+1的编码方案。对于n位要传输的信息，需要增加的冗余信息位数r必需满足 $2^r\geqslant n+r+1$ 。

0x03 流量控制

数据链路层上的流量控制是对链路上的帧的发送速率的控制，以便接收方有足够的缓冲空间来接受每一帧。

停止等待流量控制：发送方发送每一帧后都等待接收方的应答信号，此后才能发送下一帧。如果接收方不反馈应答信号，则发送方必需一直等待。这种方式每次仅发送一帧，然后就陷入等待，效率低下。

滑动窗口流量控制的特性：

发送窗口代表还没有收到对方确认信息之前最多还可以发送多少个数据帧
只有接收窗口向前滑动时，发送窗口才有可能向前滑动
当接收窗口大小为1时才能保证帧的有序接收
数据链路层的滑动窗口大小在传输过程中是固定的
从滑动窗口的概念看，几个协议只在发送和接受窗口的概念上有所差别
- 停止-等待协议：发送窗口=接收窗口=1
- 后退N帧协议：发送窗口>1，接收窗口=1
- 选择重传协议：发送窗口和接收窗口均>1

数据链路层的可靠传输通常使用确认和超时重传两种机制完成。

0x00 后退N帧协议(GBN)

当接受方检测出失序的信息帧后，要求发送方重发最后一个正确接受的信息帧之后的所有未被确认的帧。

GBN的确认机制为累积确认，即为接收方不必对收到的分组逐个发送确认，而是可以在收到几个分组后，对按序到达的最后一个分组加以确认。比如发送方发送编号为0~7的帧，接收方对第0,2,3,7个帧发送确认，就是分别对第0个帧的确认，对第1,2个帧的确认，对第3个帧的确认，对第4,5,6,7个帧的确认。

GBN中接收窗口为1，接收窗口内序号n表示现在正在等待接收序号为n的帧，如果为其他序号的帧抵达了接收窗口会直接将其丢弃，因为GBN协议是没有缓存的，所以也不存在将其缓存下来一说。发送窗口大小满足 $1\leqslant W_T \leqslant2^n-1$ ，其中 $W_T$ 为发送窗口大小，采用n个比特对帧编号。

在GBN下要想使信道利用率高，那就让帧最小单位时间内尽量多发帧。同时发送窗口的大小要依据发送帧到收到确认的总时间。

0x01 选择重传协议(SR)

选择重传不像GBN一样，不具有累积确认机制，所以哪几个帧没收到就重传哪几个帧。若采用n比特对帧编号的话，接收窗口的尺寸不应超过需要范围的一半即 $W_R \leqslant 2^{n-1}$ ，当接收窗口为最大值时，发送窗口 $W_R=W_T=2^{n-1}$

若发送窗口上边界对应的帧序号为U，则发送窗口下边界对应的帧序号 $\geqslant (U-W+1)~\text{mod}~2^k$ ，其中W为接受窗口大小，k为帧的序号长度。

0x02 计算

链路利用率

$链路利用率=\frac{t_{发送数据}}{t_{发送数据}+k\cdot t_{单向传播延迟}}\\ 其中k为系数，当链路使用停止-等待协议时，k=2 \\ 当链路采用滑动窗口协议时，k=1$

0x04 介质访问控制

静态划分信道：

信道划分介质访问控制
- 频分多路复用（FDM）：划分为多个子信道（调制为不同频率的载波），每个子信道传输一路信号，相邻信道之间需加入保护频带，此方法充分利用了传输介质的带宽，同一时间同时发送多路信号，系统效率较高，实现起来较为方便，适用于传输模拟信号
- 时分多路复用（TDM)：将物理信道按时间划分为时间片，轮流分给多个信号使用，分为TDM和STDM，假设线路速率为8kbps，有4个用户使用，TDM每个用户最高2kbps，而STDM每个用户最高8kbps，适用于传输数字信号
- 波分多路复用（WDM）：用于光纤，依据光的波长不同，此方法带宽较高
- 码分多路复用（CDM）：用不同的编码来区分，此方法既共享信道频率，又共享信道时间
  - 码分多址（CDMA）

动态划分信道：

随机访问介质访问控制（争用型协议）
- 纯ALOHA：不进行任何检测就发送数据，如果在一段时间内没有收到确认，就认为发生了冲突，等待一段随机的时间后重新发送，直至发送成功。当网络负载为G（ $T_0$ 时间所有站点发送的成功和未成功重传的帧数），网络负载为 $S=Ge^{-2G}$
- 时隙ALOHA：将所有站点的时间都统一起来，把时间划分为一段等长的时隙，每个时隙开始才能发送一个帧，吞吐量S与负载G的关系为 $S=Ge^{-G}$
- 载波侦听多路访问（CSMA）：就是比ALOHA多了一个在发送前先侦听一下信道，如果信道空闲就发送数据
  - 1-坚持CSMA：侦听到信道忙则继续坚持侦听，直到信道空闲发送数据。传播延迟对1-坚持CSMA的性能影响较大
  - 非坚持CSMA：侦听到信道忙则放弃侦听，等待一段随机时间后再重新侦听一下，直到信道空闲发送数据
  - p-坚持CSMA：侦听到信道忙，则等待下一个时隙再侦听，如果信道空闲则以概率p发送数据，以概率1-p推迟到下一个时隙再发送
- 载波侦听多路访问/碰撞检测（CSMA/CD）：适用于总线型网络或半双工网络，碰撞检测就是边发送边侦听，以判断自己发送的时候是否还有别的站点也在发送，冲突停发，随机重发。只能进行半双工通信。最小帧长为：
  
  $最小帧长=总线传播时延\times数据传输速率\times 2 \\ 收到小于最小帧长的帧将会被全部丢弃 \\ \large 最小帧长实质为在争用期发出的比特数$
  
  以太网规定的最短帧长为64bit
  
  CSMA/CD的二进制指数退避算法：
  - 确定基本退避时间，一般为2倍总线端到端的传播时延2 $\tau$
  - 定义k为重传次数，但k不超过10，当重传次数大于10时k就一直取10
  - 从离散的整数集合{0,1,…, $2^k-1$ }中随机取一个数r，重传所需要的退避时间就是r倍的基本退避时间，即 $2\tau r$
  - 当重传16次还不成功时，抛弃此帧，向高层报告
- CSMA/CA协议是改进的CSMA/CD协议以便适应无线局域网的环境，其将碰撞检测CD变成了碰撞避免CA，其有三种机制来避免碰撞：
  - 预约信道：发送之前向其他人通知自己的传输时间
  - ACK帧：接受成功向发送方返回一个ACK帧，发送方一段时间没有收到ACK帧则重发
  - RTS/CTS帧：用于解决隐蔽站问题
  预约信道和ACK帧机制是必需实现的，最后一个是可选的。
轮询访问介质访问控制：通过一个集中控制的监控站，循环地轮询每一个站点，再决定信道分配。适用于负载较高的广播信道
- 令牌传递协议：一个令牌在各个节点间按固定顺序依次传递，令牌到谁手里谁就可以发送数据，因此不会发生冲突（令牌只有一个）

其中多路复用器用于结合来自两条或多条线路的传输，以便充分利用信道。放大器用户加强宽带信号（模拟信号），中继器则是用来加强基带信号（数字信号）

码片（芯片）序列的计算：

$A和B要向C发送数据的话，A选用的码片序列要和B选用的码片序列正交\\ 也就是类似于数学上的那一套，两个向量点乘=0\\ 假设ABC三者的码片序列为(1,1,1,1),(1,-1,1,-1)和(1,1,-1,-1) \\ C收到的序列为(2,0,2,0,0,-2,0,-2,0,2,0,2)则A发送的数据的求法：\\ 首先ABC的码片序列都是4个一伙的，那就将受到的序列也分为4个4个一伙\\ 即(2,0,2,0),(0,-2,0,-2),(0,2,0,2)\\ 然后将其与A的码片序列求内积再除以码片序列的个数，拼接即为收到的数据\\ \frac{(2,0,2,0)(1,1,1,1)}{4}=1, \frac{(0,-2,0,-2)(1,1,1,1)}{4}=-1,\\ \frac{(0,2,0,2)(1,1,1,1)}{4}=1\\ 1为1，-1为0，则来自A的序列为101$

0x05 局域网

有三种：

以太网：使用最广泛，逻辑拓扑为总线型，物理拓扑为星形或拓展星形，以太网可以分为2层
- 物理层：信息的编码和译码，比特的接受和传输
- 数据链路层
  - 介质访问控制子层（MAC）：组帧拆帧、比特差错检测、寻址和竞争处理
  - 逻辑访问控制子层（LLC）：建立和释放逻辑连接，提供与高层的接口，差错控制，给帧加序号
令牌环：逻辑拓扑为环形，物理拓扑为星形
FDDI（光纤分布数字接口）：逻辑拓扑为环形，物理拓扑为双环结构

以太网：

逻辑上使用总线型拓扑结构
以广播方式发送信息
采用无连接的工作方式
不对发送数据帧编号
不要求接收方确认
尽最大努力交付数据，提供不可靠服务
由高层完成差错纠正

MAC帧：

无结束符
数据部分长度为46-1500字节，不足要填充
地址是6字节（48bit）的MAC地址

高速以太网：

100BASE-T：速率为100Mb/s，为星型拓扑结构，既支持全双工又支持半双工，可在全双工下无冲突地工作，全双工下不使用CSMA/CD协议
10Gbit以及上的以太网不使用铜线而使用光纤，只工作在全双工模式，无争用问题，故同样也不使用CSMA/CD协议

无线局域网中即使发生碰撞也要把整个帧发送完毕，有限局域网中，发生冲突则立即停止发送。

令牌环网在物理上为星型拓扑结构，逻辑上为环形拓扑结构，所有的令牌都有一个令牌持有时间，所以不可以无限地持有令牌，即便有未发完的数据。

对于参数几BASE-什么玩意，前面的数字为传输速率（Mb/s），后面如果也为数字，则使用同轴电缆，为T为双绞线，为FL为光纤对

同轴电缆（粗缆）最大长度500m，细缆最大长度185m，双绞线100m，光纤对2km

IEEE 802.11协议中数据帧的地址类型：

功能	Address1（接收端）	Address2（发送端）	Address3	Address4
IBSS	DA	SA	BSSID	未使用
To AP（基础结构型）	BSSID	SA	DA	未使用
From AP（基础结构型）	DA	BSSID	SA	未使用
WDS（无线分布式系统）	RA	TA	DA	SA

主要记住To AP和From AP两种情况！Address4可以不用看

其中：

BSS（Independent Basic Service Set）独立基本服务集
BSSID（Basic Service Set Identifier）基本服务集标识符（同RA）
DA（Destination Address）最终目的地址
SA（Sender Address）源地址
RA（Receiver Address）接收端地址
TA（Transmission Address）发送端地址

0x06 广域网

广域网是因特网的核心部分，由交换机和连接交换机的链路组成，注意是交换机不是路由器！广域网使用的协议主要在网络层，对应OSI下三层。

交换机在单个网络中转发分组，路由器在多个网络构成的互联网中转发分组

广域网数据链路层控制协议：

PPP协议：串行线路通信，面向字节，分为：
- 链路控制协议LCP：建立、配置、测试和管理数据链路
- 网络控制协议NCP：为网络层协议建立逻辑链接

PPP协议是点对点的，不是总线型，面向字节，不用CSMA/CD协议，信息段占0-1500字节，当数据部分和标志位出现重合时，需要采取措施来保证透明传输。PPP的网络层可以运行不同的网络层协议

PPP提供差错检测，不提供纠错功能，是不可靠的传输协议，不使用序号和确认机制，支持身份验证，只支持全双工，PPP可支持拨号连接（想想PPPoE），故其支持动态分配IP地址

HDLC（高级链路控制）协议：面向比特（注意与PPP区分，PPP是面向字节的）的数据链路层协议，全双工通信，所有帧采用CRC检验，对信息帧顺序编号，可防止漏发或重发，同时具有确认机制（注意与PPP协议的区别），传输可靠性高，传输控制功能与处理功能分离，具有较大灵活性，可适用于如下2种基本配置：
- 平衡配置：链路两端的站都是复合站，每个复合站都可以平等地发起数据传输，而不需要得到对方的许可，链路两端的站点具有同等的地位
- 非平衡配置：一个主机控制整个链路的工作，从站只有等主站轮询到它时才能向主站发送数据
其有三种数据操作方式：
- 正常响应方式：非平衡结构，只能由主站启动传输，从站被动地跟主站传输，从站只有接到主站的命令帧之后才能向主站发送数据
- 异步平衡方式：平衡结构，任何一个站点都可以启动数据传输，不需要对方的允许
- 异步响应方式：非平衡结构，从站在没有得到主站的允许下就可以进行传输，但是主站需要对链路进行管理
在HDLC协议中，可以根据其控制位将其帧划分为3类：
- 信息帧：传输信息
- 监督帧：用于流量控制和差错控制，执行对信息帧的确认、请求重发和请求暂停发送
- 无编号帧：用于对链路的建立、拆除和控制
HDLC以0111 1110标识每一个帧的开始和结束，当发送的数据出现连续的5个1时，会在这5个1后面添加一个0，只要有5个连续的1不管下一个是啥就必然在这5个1后面添加一个0

PPP协议为实现透明传输使用字符填充，HDLC则使用比特填充，因为PPP协议面向字符，而HDLC面向比特

0x07 各种网

	局域网	广域网	互联网
网络类型	-	单一类型网络	可连接不同类型网络
设备	直接相连	交换机	路由器
连接方式	多点接入	点到点	-
着重点	强调数据传输	强调资源共享	-
OSI层	下2层	下3层	-

可以连接不同类型网络指的是既可以连接局域网又可以连接广域网

从互联网的角度看，局域网和广域网是平等的，因为其可以连接两者

连接在一个广域网或局域网上的主机在该网内通信的时候只需要物理地址

0x08 设备

网桥：连接两个多个以太网，工作在链路层的MAC子层，其处理的数据对象是帧，网桥连接的各网段中，如果其中一个网段发生故障不影响另一个网段的正常运行。网桥收到一个帧后，检查其目的地址，如果处于不同的网段就转发给相应的网段，如果处于同一网段就将其丢弃，因为同一网段不需要借助网桥的转发目的地就能直接收到。如果一个网段的数据率是10Mb/s，使用网桥连接三个这样的网段，总的最大吞吐量就成了30Mb/s。网桥具有如下几个基本特点：
- 必需具备寻址和路径选择功能
- 从源网络接受帧，以目的网络的介质访问控制协议向目的网络发送帧
- 必要时还会进行链路层上的协议转换，即两个网段可以使用不同的协议
- 网桥不对帧做任何修改，可能对帧的封装格式做很少的修改（变换协议）
- 可以通过帧翻译互联不同类型的局域网
- 有足够大的缓存空间，因为短时间内帧的到达速度可能高于转发速度
网桥的优点：
- 过滤信息量
- 扩大物理范围
- 可使用不同的物理层
- 可互联不同类型的局域网
- 提高了可靠性
- 性能得到改善
网桥的缺点：
- 增加时延
- MAC子层没有流量控制功能（流量控制需要用到编号机制，而编号机制只有LLC子层才有）
- 只适用于用户不多通信量不大的局域网，否则容易因为传播过多的广播信息而产生广播风暴
依据路径选择方法不同分为：
- 透明网桥（选择的不是最佳路由）：按自学习算法处理收到的帧
- 源路由网桥（选择的是最佳路由）
交换机：本质上交换机就是一个多端口的网桥，利用交换机可以实现VLAN，有如下特点
- 每个端口与单个主机相连，工作在全双工模式
- 帧转发表通过自学习算法建立
- 独占传输媒体的带宽，交换机上的所有用户都共享带宽
- 交换机的总带宽随着端口的增加而增加，比如一个交换机有10个10Mb/s的端口，则交换机的总容量（总带宽）为100Mb/s
且有2种交换模式：
- 直通式：只检查目的地址（6Byte），然后马上传出去，速度较快
- 存储转发式：先缓存到高速缓存器，检查数据是否正确，不正确就将其丢弃，正确就将其发出去，但延迟较大

中继器和放大器工作在物理层，处理的对象是信号

设备	隔离冲突域	隔离广播域
集线器	不能	不能
中继器	不能	不能
交换机	能	不能
VLAN	能	能
网桥	能	不能
路由器	能	能

可以这样记忆上表：物理层设备既不隔离冲突域也不隔离广播域，链路层设备可以隔离冲突域，只有网络层设备（路由器）能隔离广播域，VLAN是一个可以由交换机实现的虚拟局域网，即可以隔离冲突域又可以隔离广播域

隔离冲突域（或广播域）的意思就是：设备的每一个端口都是一个独立的冲突域（或广播域）

在一个没有隔离冲突域的环境中，比如使用集线器连接的两台主机A和B中，从A发出的任何信息B都会收到。冲突域变大会使网络效率降低。

几种设备的传输延迟比较：

$路由器>网桥>交换机>集线器等物理层设备$