导图社区 CN 第三章 数据链路层
本人2023年研究生招生考试408分数129,将王道知识体系下的计网数据链路层最重要考点整理于此。
编辑于2023-05-22 00:14:27 浙江省数据链路层
功能
为网络层提供服务
无确认的无连接
发送方不知道是否丢失帧
有确认的无连接
发送方会重传丢失帧
有确认的有连接
可靠性最高
成帧
透明传输
不管数据是什么比特组合都应该正确传输
即数据内容不影响帧的定界
字符计数法
在帧头增加计数字段(计数字段包含自身占用的字节)
一个计数字段出错后果严重
字符填充法
发送方
在帧的头部和尾部分别插入特定字符A和B
数据部分出现
A
B
C
在其前插入转义字符C
接收方
找到前面无C的A和B
去掉A和B之间字符串中的CC/CA/CB的前一个C
比特填充法
帧首尾插入01111110
数据中连续出现5个1插入1个0
违规编码法
如曼彻斯特编码:高-高和低-低界定帧的起始和终止
只适用于冗余编码
差错控制
检错编码
都使用冗余编码
奇偶校验码
n-1位信息,1位校验
分类
奇校验码:添加校验位后n位中有奇数个“1”
偶校验码:添加校验位后n位中有偶数个“1”
只能检验奇数位的出错,检错能力50%
循环冗余码CRC
数据+帧检验序列FCS
过程
发送和接收方事先协定多项式G(x)(r+1位,阶为r)
用 数据+r位0 除以 G(x)
加法不进位,减法不借位
最高位够上1,不够上0,异或运算
余数为r位,即为FCS
接收方用帧除以G(x),余数为0则无差错
保证了帧的无差错接收
有差错的帧被丢弃,因此没有实现可靠传输
纠错编码:海明码
海明距离(码距)
码字之间
对应比特位取值不同的位数
编码集
编码集中任意两个码字的码距最小值
检测d位错编码集码距最少d+1
纠正d位错编码集码距最少2d+1
过程
确定海明码位数
信息位n,校验位k
n+k£2^k-1
如信息4位,则校验3位分别在1,2,4位置
校验关系
H1校验H3, H5, H7
H2校验H3, H6, H7
H4校验H5, H6, H7
3=2+1,5=4+1,6=4+2,7=4+2+1
校验位取值
校验的所有数据位异或
检验
各校验位与该位校验的所有信息位异或
拼接得到全0则正确,否则该数就是错误位位号
如H3出错,而对其进行校验的有H1, H2
因此由于异或关系H1, H2均变为1
此时拼接后的数位011,即为H3出错
流量控制:自动重传请求ARQ
停止—等待协议
发送帧丢失
接收方收到新的帧后发确认帧
确认帧迟到
发送方继续发送
确认帧丢失
接收方收到重复帧后丢弃,重发确认帧
发送帧和确认帧需编号
滑动窗口协议
后退N帧协议GBN
发送窗口最大为2^n-1,否则接收方无法分辨接收的是新帧还是旧帧
确认帧全部丢失
确认帧全部抵达
只按序接收帧,收到非目标帧时丢弃并返回最近的确认
可以捎带确认(自己发送数据时顺带返回确认)
选择重传协议SR
发送窗口和接收窗口不等时:发送+接收£2^n且接收£发送
接收方接收到未按序的帧时缓存,并返回该帧的确认
否定帧NAK
接收方向发送方发送
NAK中指定发送方需要重传的帧
发送窗口和接收窗口大小有限制,但数据帧序号可以使用0~2^n-1间的任意序号
窗口为1表示无缓冲
信道利用
信道利用率
发送周期=发送方从开始发送数据到收到第1个帧的确认的周期
信道利用率=发送方在1个发送周期中实际发送数据的时间/发送周期
信道吞吐率
信道利用率*发送方发送速率
发送方的实际数据传输速率
介质访问控制MAC
静态划分信道
信道划分MAC
频分多路复用FDMA
共享空间
只能传输模拟信号
用户在同样的时间中占用不同的带宽资源
时分多路复用TDMA
共享时间
适用于数字信号
把时间划分成等长时隙,每个用户占用固定序号的时隙
STDM按需动态分配时隙,单个用户最高速率为TDM的“时隙数”倍
波分多路复用WDMA
光的频分多路复用
码分多路复用CDMA
用户既共享频率,又共享时间
A和B同时向C发送数据时,将A和B的序列合起来传输,到C又分开
动态划分信道
随机访问MAC
特点
不共享空间或时间
所有用户随机发送信息,占全部带宽
分类
ALOHA
纯ALOHA
发送方
想发就发
超时则等待随机时间后重传
接收方
冲突时检测到差错,不确认
S=Ge^(-2G)
G为一段时间内所有发送方发送的帧数(包括重传的)
S为成功发送的帧数
时隙ALOHA
S=Ge^(-G)
划分时隙
将时间划分成等长时隙
发送方只有在时隙开始能发送帧
CSMA
1-坚持
载波侦听
闲:立即发送
忙:持续侦听至空闲
发生冲突
等待随机时间后重新侦听
发生冲突和侦听信道忙处理不一致
非坚持
载波侦听
闲:立即发送
忙:等待随机时间后重新侦听
p-坚持
划分时隙
载波侦听
闲:以p的概率发送
p为发送概率,不是侦听概率
忙:持续侦听(到下一个时隙开始再侦听)至空闲
发生冲突和侦听信道忙处理一致
CSMA/CD
特点
载波侦听+碰撞检测
只能进行半双工通信
适用总线型有线局域网,不适用无线局域网
载波侦听
闲:立即发送
忙:持续侦听至空闲
碰撞检测
发送过程中持续侦听信道
发送后至多2t(争用期)可知是否发生冲突(t为端到端传播时延)
最小帧长=传播时延*2*传输速率
以太网规定最短帧长为64B
发生冲突(检测到对向发来的信号)
立即停止发送
二进制指数退避算法
k=min{退避次数, 10}
第16次退避后的重传失败后抛弃帧,报告错误
从[0, 1, ..., 2^k-1]中随机选择一个作为r(最大时隙编号1023)
退避时间=r*争用期
退避计时器倒计时结束后立即重发
CSMA/CA
特点
载波侦听+碰撞避免(信道预约即碰撞避免的手段)
发送后需要等待一个帧间间隔IFS才能发送下一帧
适用于无线局域网
IFS
短SIFS
点PIFS
分布式DIFS
载波侦听
闲
该帧为站点第一个发送的帧
等待DIFS后广播RTS帧
接收方收到RTS后,等待SIFS后广播CTS帧(信道预约)
CTS指示发送方可以发送,同时指示其他站在预约期内别发送
此后两者之间的帧间间隔为SIFS
发送数据帧前
执行CSMA/CA退避算法
k=min{退避次数, 6}
从[0, 1, ..., 2^(k+2)-1]中随机选择一个作为r(最大时隙编号255)
重传有上限
信道空闲时退避计时器倒计时,计时器为0时立即重发
忙
执行退避算法
轮询访问MAC
特点
不共享空间或时间
适用于负载很高的广播信道
令牌
特殊的MAC帧,不包含信息
确保同一时刻只有一个站占用信道
在环网上按顺序依次传递
过程
发送者将持有的令牌变成数据帧发送
数据帧游荡到接收者时被接收并继续游荡
回到发送者,发送者将令牌传递给下一站点
数据链路层设备
以太网交换机
特点
隔离冲突域,多对主机无碰撞数据交换
VLAN可以隔离冲突域和广播域
每个端口直接与主机相连
交换机带宽为所有端口带宽之和
只能连接同一网络协议的网络
交换模式
直通式
只检查帧的目的地址(6字节)
存储转发式
缓存接收的帧并通过FCS检错
正确则发送,错误则丢弃
自学习(即插即用)
收到帧后
检查交换表
找不到目标则向其他所有端口广播
找到则只向对应端口转发
将来源主机MAC信息加入交换表
根据源地址学习
交换机所连主机会变化,交换表表项有有效时间
广域网
体系结构
OSI层次
物理层
数据链路层
网络层
互联网可以连接不同类型的网络(包括广域网和局域网)
PPP协议
组成
链路控制协议LCP
管理数据链路
网络控制协议NCP
每个网络层协议通过一个NCP配置逻辑连接
特点
可以同步或异步传输
默认异步(使用字符填充法成帧)
同步(使用0比特填充法成帧)
面向字节
只支持全双工点对点链路
两端可运行不同的网络层协议
FCS保证无差错接收
无法纠错,无序号和确认
不可靠传输
PPP帧
A(1)|地址(1)|控制(1)|协议(2)|数据(0~1500)|FCS(2)|B(1)
使用字符填充
A和B均为01111110(7E),为字符填充的首尾字段
转义字符为7D
点对点非总线形,因此不采用CSMA/CD,无需控制最短帧长
FCS检验除自己和首尾填充外所有的字段
局域网
体系结构
OSI层次
物理层
数据链路层
逻辑链路控制LLC
OSI的理想化设计,实际上LLC已经不起作用
对网络层提供服务
确认连接、确认无连接、无确认无连接、高速传送
媒体接入控制MAC
屏蔽物理层访问细节
以太网
特点
无连接、无确认、不可靠
曼彻斯特编码
传输介质
MAC帧
前导码(8)|目的地址(6)|源地址(6)|类型(2)|数据(46~1500)|FCS(4)
前导码
前同步码7B
帧开始定界符1B
表示后面的信息是MAC帧
不需要帧结束符
和帧的尾部不一样
数据链路层成帧需要加首部和尾部
数据
最少46B,6+6+2+46+4=64
满足争用期没有考虑前导码
校验码FCS
使用CRC冗余校验码
检验除FCS和前导码之外的整个帧
高速以太网
无线局域网
分类
有固定基站
基本服务集BSS包括一个基站和多个移动站
基站即为该BSS的接入点(AP)
移动站间通过基站通信
无固定基站
结点地位平等,所有结点都可以转发
MAC帧
接收地址+发送地址+源/目的地址
去往AP=1,来自AP=0
AP地址+源地址+目的地址
去往AP=0,来自AP=1
目的地址+AP地址+源地址
若AP与路由器相连,则会有802.3和802.11标准的帧的转换
VLAN
特点
把大局域网划分成逻辑上的VLAN,每个VLAN是一个广播域
不同交换机的主机可能加入同一VLAN
VLAN标签
以太网帧的源地址和类型字段间插入的4B
8100(标明此帧为802.1Q帧)+4bit(无用)+12bit(VID)
最大帧长由1518B变为1522B(不会考虑前导码)
普通帧加入VLAN标签变为802.1Q帧后,FCS需要重新计算
不同交换机的相同VLAN间转发帧
交换机间发送的帧为802.1Q
交换机内发送的帧为普通帧
主机不知道自己的VID
局域网和广域网
局域网
局域网主要有以太网和无线局域网,使用不同的帧
每个以太网为一个广播域(交换机不能隔离广播域)
VLAN相当于把一个以太网划分成多个小的以太网
每个VLAN为一个广播域
VLAN的帧和以太网帧差不多
因此不同交换机的相同VLAN上的主机可传输信息
广域网
主要是因特网
点对点传输,不是广播
交换机泛洪
交换表中不存在目的主机时向除发送端口外的所有端口发送
不会考虑其他关系(如交换机一个端口只连接一个主机,目的地址不可能在该端口)
CSMA
CSMA/CD和CSMA/CA适用网络(传输介质)不同,故载波侦听方式不同
CSMA/CA可以使用信道预约(即RTS和CTS)解决隐蔽站问题,也可以不使用
CSMA/CA发送第一个帧前等待DIFS,其余等待SIFS
第一个帧可以为RTS或者数据帧