数据链路层
概念
结点:主机、路由器
链路:网络中两个结点之间的物理通道,链路的传输介质主要有双绞线、光纤和微波;分为有线链路和无线链路
数据链路:网络中两个结点之间的逻辑通道,把实现控制数据传输协议的硬件和软件加到链路上就形成了数据链路
帧:链路层的协议数据单元,封装网络层数据报
数据链路层负责通过一条链路从本结点向另一个物理链路直接相连的相邻结点传输由网络层传下来的数据报
功能
数据链路层在物理层提供服务的基础上面向网络层提供服务,将源自网络层的数据可靠的传输到相邻结点的目标机网络层。主要作用为加强物理层传输原始比特流的功能,将物理层提供的可能出错的物理连接改造为逻辑上无差错的数据链路,使之对网络层表现为一条无差错的链路
为网络层提供服务
无确认无连接服务:不会事先连接相邻结点,收到数据后不会返回确认
有确认无连接服务:不会事先连接相邻结点,收到数据后返回确认
有确认面向连接服务:事先连接相邻结点,收到数据后返回确认
链路管理:连接的建立、维持、释放
组帧
流量控制
差错控制
组帧
封装成帧:发送方将一段数据报前后部分添加首部和尾部,封装后称为帧。帧的首部和尾部包含很多控制信息,用以做帧定界
帧同步:接收方在比特流中区别帧的开始和结束。
透明传输:不管数据是怎样的比特组合,都可以在数据链路层上传送,数据链路层只管传。如果有一段数据和帧控制信息重复了,需要对数据做处理,防止接收方误判;同时保证透明传输(数据链路层不管是啥,只管传)
字符计数法
帧首部使用一个计数字段来表明帧内字符数
一个计数字段错误时,后面数据全部出错
字符填充法
根据特定协议,将帧首部和尾部确定为特定二进制数,放在首部和尾部的字节中
- 传送的帧由文本文件组成时(键盘上输入的 ASCLL 码),和二进制数不同,可以透明传输
- 传送的帧是非 ASCLL 码的文本文件组成时(二进制的图像或程序),采用字符填充方法实现透明传输
发送时在与帧控制信息重复的数据前添加转义字符,接收后去掉
零比特填充法
设置帧首部和尾部为特定的 01111110(6个1)。发送方在数据报中扫描到连续的 5 个 1,就在后面填入 1 个 0(扫描到就填入 0,不管后面原来是不是 0);接收方扫描帧判定帧首部和尾部(帧首部和尾部是 6 个 1,不同于数据报里),然后对数据报进行扫描,发现连续的 5 个 1 就删除后面的 1 个 0,保证了透明传输
所以即使数据报中有和帧首部尾部一样的 01111110,也会因为有 5 个 1 而填充 0,起到判断作用
违规编码法
曼彻斯特编码中明确由高到低表示 1,由低到高表示 0,高—高和低—低是错误的编码,就用这两个编码作为帧首部和尾部
差错控制
由噪声引起差错。分为全局性和局部性
全局性:线路本身电气特性所产生的随机噪声,信道固有,随机存在
提高信噪比来减少或避免干扰(对传感器下手)
外界特定的短暂原因所造成的冲击噪声
利用编码技术解决
控制差错可用奇偶校验码、循环冗余码、海明码控制
奇偶校验码
校验原理
信息 | A | B | C | D |
---|---|---|---|---|
编码1 | 00 | 01 | 10 | 11 |
编码2 | 100 | 001 | 010 | 111 |
码字:由若干位代码组成的一个字(00 组成 A 或者 100 组成 A)
两个码字间的距离:将两个码字逐位进行对比,具有不同的位的个数(编码 1 中 A 和 B 相距 1,编码 2 中 A 和 B 相距 3,B 和 D 相距 6)
码距:一种编码方式中可能有若干个合法码字,各合法码字间的最小距离(编码 1 中为 1,编码 2 中最小为 2)
当码距为1时,无检错能力;为2时,有检错能力;为3时,有检错能力,可能有纠错能力
奇校验码:整个校验码(有效信息位和校验位)中 “1” 的个数为奇数
偶校验码:整个校验码(有效信息位和校验位)中 “1” 的个数为偶数
1001101 | 1010111 | |
---|---|---|
奇校验 | 11001101(保证奇数个1) | 01010111(保证奇数个1) |
偶校验 | 01001101(保证偶数个1) | 11010111(保证偶数个1) |
局限性:同时有两个位出错,接收方可能认为是正确的
硬件实现
求偶校验位:对编码的每一位进行异或运算(第一次运算用前两个,后面的运算用前一次的结果和后一位编码),最终得到的结果为偶校验位
例:1001101 经过异或结果为 0,则偶校验为 01001101
进行偶校验:对所有位进行异或,最终结果为 1 说明出错
海明校验码
思路:将信息位分为多个组,每个组进行偶校验——>多个校验位标注出错位置
校验位数量:
设信息位为 n
设校验位为 k,有
满足:
1010的海明码求解步骤:
确定海明码的位数
n=4——>k=3
设信息位为
,校验位 海明码为
确定校验位分布
校验位
在海明码位号为 上 即1,2,4,8,16等
求校验位的值
纠错
1位纠错能力,2位检错能力
加上“全校验位”,对海明码整体进行偶校验
知识回顾
循环冗余校验码
原理:数据发送、接收方约定一个除数,K个信息位+R个校验位作为被除数,接收数据后利用除法检测余数是否为0
例题:设生成多项式为
确定K、R以及生成多项式对应的二进制码
由
得出对应的二进制码为 1101
K=信息码长度=6,R=检验码长度=生成多项式最高次幂=3
N=校验码长度=K+R=9
移位
信息码左移R位,低位补0
即为
101001 000
相除
对移位后的信息码用生成多项式对应的二进制码进行模2除法,产生余数
产生的余数为
001
,对应的CRC码为101001 001
检错和纠错
发送:101001001 记为
接收:101001001 用1101进行模2除法——>余数为000,代表没有出错
接收:101001011 用1101进行模2除法——>余数为010,代表出错
一般用来检错,不用来纠错
流量控制
较高的发送速度与较低的接收速度不匹配,造成传输出错。
当接收端接收不下时,不给发送端回复确认帧
停止—等待协议
为了解决比特出错,丢包(物理线路故障,设备故障,病毒攻击,路由信息错误),实现流量控制
每发送完一个帧就停止发送,等待对方的确认,收到确认后发送下一帧
无差错情况:
有差错情况:
数据帧丢失或检测到帧出错
ACK丢失
ACK迟到
信道利用率:发送方在一个发送周期内,有效发送的数据所需要的时间占整个发送周期的比率
信道吞吐率:信道利用率*发送方的发送速率
例题:一个信道的数据传输率为4Kb/s,单向传播时延为30ms,如果使停止-等待协议的信道最大利用率达到80%,要求数据帧长度至少为()
后退N帧协议(GBN)
发送流程:
- 发送窗口发出第0帧,接着发出第1帧……
- 接收窗口接收到第0帧,回复确认并前进一组
- 发送窗口得到新一组可以发送的帧,此时信道上有已经发送的帧等待接收
- 接收窗口接收等待在信道上的帧,并回复确认,继续前进
发送方的响应:
- 上层的调用:检查发送窗口空余:未满,产生帧并发送;已满,返还数据到上层,等待后在重新发送
- 收到ACK:采取累计确认的方式,回传n号帧的确认,表示接收方收到n号帧及其之前的全部帧
- 超时事件:发生丢失和时延过长帧时,利用定时器确认,并重发已发送但未被接收方确认的帧
接收方的相应:
- 返回ACK:正确且按序收到n号帧,返回一个n号帧的ACK(累计确认),并交付帧中的数据到上层
- 处理错误:丢弃不正确/乱序的帧,返回一个最近的正确且按序的帧的ACK,方便发送方重传
滑动窗口长度:对采用n个比特对帧编号,窗口长度应满足
假设n为2,即有00,01,10,11四种情况,即0,1,2,3四种帧。当窗口长度超过上限,为4,第一轮,正确发送4个帧,累计确认后返回3的ACK,然后第二轮四个帧全部错误,因为上一个返回的是3号帧的ACK,系统无法判断这是发送成功了;还是失败了,传回的是上轮成功时发回的ACK
性能分析
优点:连续发送数据帧而提高信道利用率
缺点:重传时需要重传错误帧后面的正确的帧,降低传送效率
选择重传协议(SR)
设置单个确认,加大接收窗口,设置接收缓存,用来缓存乱序到达的帧
发送流程:
发送方的响应:
- 上层的调用:从上层接收到数据后,检查窗口中是否有可用于该帧的序号,存在则发送数据帧,否则缓存数据/返回给上层,之后再传输
- 收到ACK:ACK对应的序号在窗口内,标记为已接收。该序号为窗口下界(最左边的序号),滑动窗口使下界为最近一个未接收的序号。窗口移动后存在有序号且未发送的帧,则进行发送
- 超时事件:发生丢失和时延过长帧时,利用定时器确认,重发这个帧
接收方的相应:
- 返回ACK:发送方传来一个正确且序号在接收窗口中的帧,如果这个帧的序号是接收窗口的下界,则接收帧并返回确认帧,然后滑动窗口至正确位置;如果这个帧乱序,则接收帧并缓存,返回确认帧
- 处理错误:当接收到发送方传来的,在接收窗口之前的帧,只需要重新传回对应帧号的ACK(接收到此帧并返回的ACK丢失,发送方以为传送失败,重传)
滑动窗口长度:
同GBN,过长时无法判断是新帧还是旧帧
传输数据使用的两种链路
点对点链路:两个相邻节点通过一个链路相连,没有第三者。应用于PPP协议,常用于广域网
广播式链路:所有主机共享通信介质。应用于早期的总线以太网、无线局域网,常用于局域网
广播式链路的经典拓扑结构是总线型和星型
总线型
星型
二者中A发出通信数据,都被其他的节点接受。经过判断后只有特定节点会处理相应通信数据,其他节点抛弃
介质访问控制
采取一定措施,使得两对节点之间的通信不会发生相互干扰的情况
信道划分介质访问控制
将使用介质的每个设备与来自同一信道上的其他设备的通信隔离开,把时域和频域资源合理地分配给网络上的设备
多路复用技术:把多个信号组合在一条物理信道上进行传输,使得多个计算机或终端设备共享信道资源,提高信道利用率
把一条广播信道,逻辑上分成几条用于两个节点之间通信的互不干扰的子信道,实际就是把广播信道转变成点对点信道
频分多路复用FDM
频分复用的所有用户在同样的时间占用不同的带宽(频率带宽)资源,用户在分配到一定的频带后,在通信过程中自始至终都占用这个频带
时分多路复用TDM
将时间划分为一段段等长的时分复用帧(TDM帧)。每一个时分复用的用户在每一个TDM帧中占用固定序号的时隙,所有用户轮流占用信道
统计时分复用STDM
在上面的TDM中,在同一个TDM帧中,如果A、B、C都没有使用,D还是需要在每次的TDM帧中等待,降低了信道利用率
改进后的TDM为STDM
- 每一个STDM帧中的时隙数小于连接在集中器上的用户数。
- 各用户有了数据就随时发往集中器的输入缓存,然后集中器按顺序依次扫描输入缓存,把缓存中的输入数据放入STDM帧中
- 一个STDM帧满了就发出
- STDM帧不是固定分配时隙,而是按需动态分配时隙
当某一个用户使用频率远大于其他用户时,这个用户可以占据更多的STDM帧,相当于提高自己的传送速率到整个信道的传输速率
假设信道传输速率是8000b/s,一个TDM帧上有四个时隙,那么A用户每秒的传输速率就是2000b/s
当使用STDM时,A用户使用频率大于其他用户,可以占用更多的STDM帧,那么A用户最大传输速率可以达到8000b/s
波分多路复用WDM
波分多路复用就是光的频分多路复用,在一根光纤中传输多种不同波长(频率)的光信号,由于波长(频率)不同,所以各路光信号互不干扰,最后再用波长分解复用器将各路波长分解出来
❗码分多路复用CDM
码分多址CDMA是CDM的一种方式
一个bit分为多个码片/芯片,每一个站点被指定一个唯一的m位的芯片序列
发送1时站点发送芯片序列,发送0时站点发送芯片序列反码(通常把0写作-1)
①如何不打架:多个站点同时发送数据的时候,要求各个站点芯片序列相互正交(即相乘并除以长度等于0)
②如何合并:各路数据在信道中被线性相加
③如何分离:合并的数据和源站规格化内积
随机访问介质访问控制
ALOHA协议
纯ALOHA协议
不监听信道,不按时间槽发送,随机重发,想发就发
冲突检测:发生冲突后,接收方会检测出差错,然后不予确认,发送方在一定时间内收不到接受确认就判断发生冲突
冲突解决:超时后等一随机时间再重传
时隙ALOHA协议
把时间分成若干个相同的时间片,所有用户再时间片开始时刻同步接入网络信道,若发生冲突,必须等到下一个时间片开始时刻再发送(在且仅在时间片开始时刻发送帧)
对比
- 纯ALOHA比时隙ALOHA吞吐量更低,效率更低
- 纯ALOHA想发就发,时隙ALOHA只有在时间片段开始时才能发
CSMA协议
载波监听多路访问协议CSMA(carrier sense multiple access)
CS:载波监听,每个站在发送数据之前先检测一下总线上是否有其他计算机在发送数据
如何检测:当几个站同时在总线.上发送数据时,总线上的信号电压摆动值将会增大(互相叠加)。当一个站检测到的信号电压摆动值超过一定门限值时,就认为总线上至少有两个站同时在发送数据,表明产生了碰撞, 即发生了冲突
MA:多点接入,表示许多计算机以多点接入的方式连接在一根总线上
协议思想:发送帧之前监听信道
1-坚持CSMA
如果一个主机要发送信息,那么它先监听信道
空闲则直接传输,不必等待;忙则一直监听,直到空闲马上传输
如果有冲突,等待随机时间后重复上述操作
优点:信道空闲就马上传输,避免信道利用率的损失
缺点:如果有两个或两个以上的站点有数据要发送,冲突不可避免(两个站点发现信道忙,然后一起监听;发现空闲后都打算发送信息,这时候就冲突了)
非坚持CSMA
如果一个主机要发送信息,那么它先监听信道
空闲则直接传输,不必等待;忙则等待一个随机时间之后再进行监听
优点:采用随机的重发延迟时间可以减少冲突发生的可能性
缺点:可能存在各站点都在延迟等到,但是信道空闲,降低了信道利用率
p-坚持CSMA
如果一个主机要发送信息,那么它先监听信道
空闲则以p的概论直接传输,1-p的概率等待到下一个时间槽再传输;忙则等待一个随机时间之后再进行监听
p是一个根据现实情况人为设置的参数
优点:通过概论p直接传输,减少冲突发生的可能性;也保证信道空闲时有信息传输,避免信道利用率的损失
缺点:发生冲突后会坚持把数据帧发送完,造成浪费
对比
❗CSMA/CD协议
载波监听多路访问/碰撞检测协议CSMA/CD(carrier sense multiple access with collision detection)
CSMA/CD 用于总线型的以太网
CS:载波监听,每个站在发送数据之前和发送数据时先检测一下总线上是否有其他计算机在发送数据
MA:多点接入,表示许多计算机以多点接入的方式连接在一根总线上(总线型网络)
CD:碰撞检测,边发送边监听,适配器边发送数据边检测信道上信号电压的变化情况,以便判断自己在发送数据时其他站是否也在发送数据(半双工网络)
为什么要边发送边监听?
电磁波在总线上以有限速率传播,站点A发送数据并还未到达站点B,站点B会以为信道空闲,实际上信道被占用
即传播时延对载波监听有影响
如何确定碰撞后的重传时机?
采用截断二进制指数规避算法
例题:在以太网的二进制回退算法中,在11次碰撞后,站点会在[ 0 ~ ? ]之间选择一个随机数
重传次数=11,大于10,k值选择10
范围是
,即 中任选一个
最小帧长问题
防止检测到碰撞时,帧已经发送完毕
冲突窗口最大为2τ,只要传播时延大于2τ即可
CSMA/CA协议
载波监听多路访问/碰撞避免协议CSMA/CD(carrier sense multiple access with collision avoidance)
CSMA/CA 用于无线局域网
工作流程:
- 发送数据前,先检测信道是否空闲
- 空闲则发出RTS(request to send),RTS包括发射端的地址、接收端的地址、下一份数据将持续发送的时间等信息;信道忙则等待
- 接收端收到RTS后,将响应CTS(clear to send)
- 发送端收到CTS后,开始发送数据帧(同时预约信道:发送方告知其他站点自己要传多久数据)
- 接收端收到数据帧后,将用CRC来检验数据是否正确,正确则响应ACK帧
- 发送方收到ACK帧就可以进行下一个数据帧的发送,若没有收到ACK帧则一直重传至规定重发次数为止(采用二进制指数退避算法来确定随机的推迟时间)
- 接收端响应其他站点的RTS并传回CTS
CSMA/CD与CSMA/CA的对比
相同点:
- CSMA/CD与CSMA/CA机制都从属于CSMA的思路,其核心是先监听在发送。换言之,两个在接入信道之前都须要进行监听。当发现信道空闲后,才能进行发送
不同点:
- 传输介质不同:CSMA/CD用于总线式以太网(有线),而CSMA/CA用于无线局域网(无线)
- 载波检测方式不同:因传输介质不同,CSMA/CD与CSMA/CA的检测方式也不同。CSMA/CD通过电缆中电压的变化来检测,当数据发生碰撞时,电缆中的电压就会随着发生变化;而CSMA/CA采用能量检测(ED)、载波检测(CS))和能量载波混合检测三种检测信道空闲的方式
- CSMA/CD检测冲突,CSMA/CA避免冲突,二者出现冲突后都会进行有上限的重传
轮询访问介质访问控制
轮询协议
主节点轮流询问从属节点是否发送数据,轮询一轮后从头继续下一轮
优点:
- 不会发生冲突
- 每次只有一台从属节点发送数据,占据全部信道
缺点:
- 轮询开销
- 等待延迟:靠前的从属节点不发送数据也需要被轮询;靠后的需要发送数据的从属节点必须等待
- 单点故障:主节点宕机后乐子就大了
❗令牌传递协议
令牌:一个特殊格式的MAC控制帧,不含任何信息
工作流程:
- 当前持有令牌、且需要传输数据的主机,修改令牌的控制位,并附上需要传输的数据,传递出令牌
- 令牌在令牌环中依次传递,每台主机查看一下令牌,看是不是给自己发送的数据:如果是就复制数据并传递出令牌;不是则直接传递
- 发送数据的主机在轮递令牌一圈后回收令牌,查看令牌中的数据是否正常接收,若不正常则重传
- 若主机无数据传输或超出令牌持有时间,传递令牌到下一台主机
优点:
- 持有令牌则可以控制信道的使用,保证同一时刻只有一个节点独占信道
- 每个节点在令牌持有时间内获得发送数据的权利,防止一个节点一直占据令牌,其他节点无法获得令牌
缺点:
- 令牌开销:令牌丢失需要产生新令牌
- 等待延迟:靠后的需要发送数据的节点必须等待拥有令牌
- 单点故障:令牌环网中任何一个节点宕机会导致环网断裂,无法传递令牌
特点:
- 应用于令牌环网(物理星型拓扑,逻辑环形拓扑)
- 常用于负载较重,通信量较大的网络
局域网
Local Area Network,简称LAN,指在某一区域内由多台计算机互联成的计算机组,使用广播信道
特点:
- 覆盖的地理范围较小,只在一个相对独立的局部范围内联,如一座或集中的建筑群内
- 使用专门]铺设的传输介质(双绞线、同轴电缆或无线)进行联网,数据传输速率高(10Mb/s ~ 10Gb/s)
- 通信延迟时间短,误码率低,可靠性较高
- 各站为平等关系,共享传输信道
- 多采用分布式控制和广播式通信,能进行广播和组播
决定局域网的主要要素为:网络拓扑,传输介质与介质访问控制方法
拓扑结构
传输介质
有线局域网:双绞线、同轴电缆、光纤
无线局域网:电磁波
介质访问控制方法
CSMA/CD:常用于总线型局域网,也用于树型网络
令牌总线:常用于总线型局域网,也用于树型网络。
它是把总线型或树型网络中的各个工作站按一定顺序如按接口地址大小排列形成一个逻辑环。只有令牌持有者才能控制总线,才有发送信息的权力
令牌环:用于环形局域网,如令牌环网
分类
- 以太网:以太网是应用最为广泛的局域网,包括标准以太网(10Mbps))、快速以太网(100Mbps)、千兆以太网(1000 Mbps)和10G以太网,它们都符合IEEE 802.3系列标准规范。逻辑拓扑总线型,物理拓扑是星型或拓展星型。使用CSMA/CD
- 令牌环网:物理上采用了星形拓扑结构,逻辑上是环形拓扑结构
- FDDI网:物理上采用了双环拓扑结构,逻辑上是环形拓扑结构
- ATM网:较新型的单元交换技术,使用53字节固定长度的单元进行交换
- 无线局域网(WLAN):IEEE 802.11标准
MAC子层和LLC子层
以太网
基带总线局域网规范,使用CSMA/CD技术
特点:
- 造价低廉
- 应用最广泛的局域网技术
- 比令牌环网、ATM网便宜,简单
- 满足网络速率要求:10Mb/s ~ 10Gb/s
无连接:发送方和接收方之间无握手过程
不可靠:不对发送方的数据帧编号,接收方不向发送方进行确认,差错帧直接丢弃,差错纠正由高层负责
即以太网只实现无差错接收,不实现可靠传输
传输介质:双绞线+集线器
拓扑结构:物理上星型(集线器),逻辑上总线型
以太网MAC帧
无线局域网
MAC帧头格式
广域网
广域网(WAN, Wide Area Network),通常跨接很大的物理范围,所覆盖的范围从几十公里到几千公里,它能连接多个城市或国家,或横跨几个洲并能提供远距离通信,形成国际性的远程网络
PPP协议
点对点协议PPP(Point-to-Point Protocol)是目前使用最广泛的数据链路层协议,用户使用拨号电话接入因特网时一般都使用PPP协议
只支持全双工链路
需要满足的要求:
- 简单:对于链路层的帧, 无需纠错,无需序号,无需流量控制
- 封装成帧:帧定界符
- 透明传输:与帧定界符一样比特组合的数据应该如何处理:异步线路用字节填充,同步线路用比特填充
- 多种网络层协议:封装的IP数据报可以采用多种协议
- 多种类型链路:串行/并行, 同步/异步,电/光…
- 差错检测:错就丢弃
- 检测连接状态:链路是否正常工作
- 最大传送单元:数据部分最大长度MTU
- 网络层地址协商:知道通信双方的网络层地址
- 数据压缩协商
不需要满足的要求:
- 纠错
- 流量控制
- 序号
- 不支持多点线路
功能:
- 一个将IP数据报封装到串行链路(同步串行/异步串行)的方法
- 链路控制协议LCP:建立并维护数据链路连接(比如身份验证)
- 网络控制协议NCP:PPP可支持多种网络层协议,每个不同的网络层协议都要一个相应的NCP来配置,为网络层协议建立和配置逻辑连接
状态图
帧格式
协议字段:0x0021
表示IP数据报;0xc021
表示链路控制数据;0x8021
表示网络控制数据
FCS字段:也是CRC字段,表示循环冗余校验码
HDLC协议
高级数据链路控制(High-Level Data Link Control或简称HDLC),是一个在同步网上传输数据、面向比特的数据链路层协议,它是由国际标准化组织(ISO)根据IBM公司的SDLC(SynchronousData Link Control)协议扩展开发而成的,采用全双工通信
数据报文可透明传输,用于实现透明传输的0比特插入法易于硬件实现
所有帧采用CRC检验,对信息帧进行顺序编号,可防止漏收或重份,传输可靠性高。
主站、从站、复合站
- 主站的主要功能是发送命令(包括数据信息)帧、接收响应帧,并负责对整个链路的控制系统的初启、流程的控制、差错检测或恢复等
- 从站的主要功能是接收由主站发来的命令帧,向主站发送响应帧,并且配合主站参与差错恢复等链路控制
- 复合站的主要功能是既能发送,又能接收命令帧和响应帧,并且负责整个链路的控制
三种数据操作方式:
- 正常响应方式
- 异步平衡方式
- 异步响应方式
帧格式
两种协议的对比
链路层设备
物理层扩展以太网
链路层扩展以太网
网桥:根据MAC帧的目的地址对帧进行转发和过滤。当网桥收到一个帧时,并不向所有接口转发此帧,而是先检查此帧的目的MAC地址,然后再确定将该帧转发到哪一个接口, 或者是把它丢弃(即过滤)