数据链路层服务

Scroll Down

数据链路层服务

概述

数据链路层是一段一段的链路如何实现节点到节点之间的数据传输.

术语:

  • 主机和路由器都称为:结点

  • 连接相邻结点的通信信道:链路(links)

    • 有线链路
    • 无限链路
    • 局域网
  • 链路层(第2层)数据分组:称为数据帧或者,用于封装网络层数据报

数据链路层负责通过一条链路从一个结点向另一个物理链路直接相连的相邻结点传输数据报

链路层服务

  • 组帧:

    • 封装数据报构成数据帧,加首部和尾部,头部可能有链路层地址的信息,尾部有些差错编码的信息
    • 实现帧同步,通过特定的比特串或者特殊字符来定位一个数据帧的开始与结束.还需要考虑到怎么避免和帧中的数据的歧义,在数据中有帧定界的字符,通过字符填充或比特填充对其进行转义
  • 链路接入:

    • 如果是共享介质,需要解决信道接入问题
    • 帧首部中的MAC地址,用于标识帧的源和目的,**不同于IP地址!**作为MAC地址,与IP地址有很大的不同,一个是网络层地址,一个是链路层地址
  • 相邻结点间的可靠交付(可靠传输)

    • 在低误码率的有线链路上很少采用(如光纤,双绞线等),可能不采用非常可靠的数据帧交付方式
    • 无线链路:误码率高,通常需要使用可靠的数据交付来保证链路上的传输是可靠的
  • 流量控制:

    • 协调相邻的发送结点和接收
  • 差错检测:

    • 应对信号衰减或者噪声银企的比特差错
    • 接收端检测到差错,通知发送端重传或者直接丢弃帧
  • 差错纠正:

    • 接收端直接纠正比特差错
    • 确认重传-也是一种纠正差错方式
  • 全双工和半双工通信控制:

    • 全双工:链路两端结点同时双向传输
    • 半双工:链路两端结点交替双向传输

并不是所有的链路层协议需要提供上述的这些服务,链路层在现实中最常见的实现,例如:以太网网卡,802.11网卡,同时实现了链路层和物理层

帧的发送与接收

image-20200207195044436

发送端:

  • 将数据报封装成帧
  • 增加差错检测比特,实现可靠数据传输和流量控制等

接收端:

  • 检测差错,实现可靠数据传输和流量控制等
  • 提取数据报,交付上层协议实体

差错编码

差错编码的基本原理:

  • 在数据中增加一些冗余信息,冗余信息建立起了数据比特与比特之间的一种关联关系,例如D->DR,其中R为差错检测与纠正比特,接收端去检查对应关系是否匹配

image-20200207195422593

差错编码不能保证100%可靠!

差错编码的检错能力

  • 差错编码可以分为检错码与纠错码

    • 检错码只能发现错误,无法纠正
    • 纠错码可以检错并且纠错
  • 对于检错码,如果编码集的汉明距离ds=r+1,则该差错编码可以检测r位的差错

    • 汉明距离:两个码字不同对应比特位不同的位数,位异或运算
    • 编码集的汉明距离:编码集里的所有的有效码字,任意两个码字之间汉明距离的最小值
    • 例如:编码集{0000,0101,1010,1111}的汉明距离ds=2,可以100%检测1比特的差错
  • 对于纠错码,如果编码集的汉明距离ds=2r+1,则该差错编码可以纠正r位测差错,纠错码的原理是将该无效的码字纠错为距离它最近的码字

    • 例如,编码集{000000,010101,101010,111111}的汉明距离ds=3,可以实现纠正1比特的差错,如100010与101010距离最近,则将其纠正为101010.基于概率最大化的原则

奇偶校验码

1比特校验位:

  • 在数据的基础上,增加一个校验位,如果是奇校验,则使加上该校验位1的位数是奇数个,奇数为1,偶数为0,如果是偶校验,则1的位数是偶数个.可以实现奇数位的差错,检错率的概率为:50%
    • 好处是无论数据多大只需要加一个比特位,效率很高

二维奇偶校验:将数据组织成一个二维的矩阵形式,每一行和每一列增加一个校验位,构造成一个二维奇偶校验

image-20200207202003452

  • 检测所有奇数位差错,部分偶数位差错
  • 假如错了两位,错在不同的列上,则偶数位的错误也可发现
  • 可以纠正同一行或者同一列的奇数位错

发送端:

将数据划分为16位的二进制整数序列,进行补码求和,再取反码,获得checksum字段,然后放入分组(UDP,TCP,IP)的校验和字段

接收端:

与发送端相同方法计算,计算得到的checksum,如果按照发送端的方法计算出来,取的16位全0,或者sum为16位全1,则证明无措,只要有1位不全0或者不全1则证明出错

循环冗余校验码(CRC)

  • 检错能力更强大的差错编码

  • 将数据比特串看做一个二进制的数据,表示为D

  • 选择一个r+1位的生产比特模式,G

  • 目标:选择r位的CRC比特,记做R

    • <D,R>刚好可以被G整除(模2除)
    • 接收端检测:利用G除<D,R>,结果全为0的话,无错,否则就有错!
    • 只要找到一个优良的G,可以检测所有突发长度小于r+1位差错
  • 在实际网络中广泛使用(以太网,802.11 WIFI,ATM)

多路访问控制(MAC)协议

两类链路:

  • 点对点链路,故名思意,只连接一个相邻的结点,不会连接第三个结点,

    • 例如拨号上网协议等
    • 以太网交换机与主机间的点对点链路
  • 广播链路(广播共享链路)

    • 物理介质是被共享的
    • 局域网中多见,早起的总线以太网
    • 共享WIFI
    • 共享卫星网络

采用单一共享广播信道来进行通信,在这类链路中,如果有两个或两个以上结点同时传输,势必会造成干扰,称为冲突,结点同时接收到两个或者多个信号->接受失败!

因此在使用广播链路网络中,需要使用一种协议,就是我们所说的多路访问控制(MAC,Multiple Access Control protocol)协议:

  • 采用分布式算法决定结点如何共享信道,即决策结点何时可以传输数据
  • 必须基于信道本身,通信信道共享协调信息!

理想的MAC协议

假设给定:速率为R bps的广播信道

期望:

  1. 当只有一个结点希望传输数据时,它可以以速率R发送
  2. 当有M个结点期望发送数据时,每个结点平均发送数据的平均速率是R/M
  3. 完全分散控制:无需特定结点协调,无需时钟,时隙同步
  4. 越简单越好,因为协议越复杂,开销就越大

MAC协议分类

三大类:

  • 信道划分(channel partitioning)MAC协议

    • 多路复用技术,将信道划分成资源片,每个连接都使用对应的资源片,就不会有冲突问题
    • TDMA,FDMA,CDMA,WDMA协议等
  • 随机访问(random access)MAC协议

    • 在局域网中很常见
    • 信道不划分,允许冲突,任何信道想使用就可以使用全量的信道资源
    • 一定会有冲突之后的恢复机制
  • 轮转(taking turns)MAC协议

    • 结点轮流使用信道
    • 保证在使用信道过程中不发生冲突,每个信道在使用信道时是使用信道所有资源

信道划分MAC协议

TDMA:time division multiple acess

  • 周期性接入信道
  • 每个站点在每个周期,占用固定长度的时隙
  • 未用时隙时就空闲

image-20200207223401303

FDMA:frequency division multiple access

  • 信道频谱划分若干频带
  • 每个站点分配一个固定的频带
  • 无传输频带空闲
  • 类似于有线电视

image-20200207223456729

随机访问MAC协议

当结点要发送分组时:利用信道全部数据速率R发送分组,没有事先的结点间协调,任何一个结点在任意时间都可能发送数据帧

多个结点同时传输:导致冲突

随机访问MAC协议需要定义:

  • 如何检测冲突
  • 一旦发生冲突后,如何从冲突中恢复(例如延迟重传)

典型的随机访问MAC协议:

  • 时隙ALOHA协议
  • 纯ALOHA协议
  • CSMA,CSMA/CD,CSMA/CA
时隙ALOHA协议

假定:

  1. 所有数据帧大小相同
  2. 时间被划分为登场的时隙(每个时隙可以传输1个帧)
  3. 结点只能在时隙开始时刻发送帧
  4. 结点间时钟同步
  5. 如果多个结点在同一时隙发送数据帧,结点立刻检测到冲突(例如发送时需要对方返回确认,没收到确认就认为是冲突了)

运行:

  • 当结点有新的帧时,在下一个时隙发送
    • 如果没有检测到冲突:发送成功,该结点可以在下一个时隙继续发送新的帧
    • 如果检测到冲突:本次发送失败,在下一个时隙以概率p重传该帧,直至成功

时隙ALOHA协议运行示例

假设有三个结点共享一个链路,在示意图中可以看出1,2,3在C时隙冲突,在E时隙空闲,直至S时隙发送第2个数据帧发送成功

image-20200207224532638

优点:

  • 单个结点活动时,可以连续以信道全部速率传输数据
  • 高度分散化:只需要同步时隙,不需要任何结点来同步
  • 协议简单

缺点:

  • 很容易造成冲突,浪费时隙
  • 会具有空闲时隙(如图中的E时隙)
  • 结点也许能以远小于分组传输时间检测到冲突
  • 必须要求所有结点之间时钟必须是同步的

效率:长期运行时,成功发送帧的时隙所占所有帧的比例,最大效率是37%

image-20200207225043937

纯Aloha协议

也称为非时隙Aloha协议:更加简单,无需时钟同步,当有新的帧生成时,立即发送帧,冲突的可能性加大,

image-20200207225341613
image-20200207225520354

所以纯Aloha协议发送的效率一定低于时隙Aloha协议

载波监听多路访问协议-CSMA(carrier sense multiple access)

和Aloha协议的改进:

  • 发送帧之前,监听信道(载波)

    • 信道空闲:发送完整帧
    • 信道忙:推迟发送
      • 1-坚持CSMA,一直监听信道,信道空闲时就立即发送消息
      • 非坚持CSMA,当发现信道忙时,不监听信道,随机等待一段时间后再监听信道
      • P-坚持CSMA,以概率p监听信道,以1-p概率不监听信道
  • 冲突可能仍然会发生:信号传播有延迟 或者 两个数据帧都在监听信道,两者都立即发送数据,此时还是会冲突

CSMA/CD 带有冲突检测的载波监听多路协议

CSMA/CD:CSMA with Collision Detection

  • 短时间内可以检测到冲突
  • 冲突后传输中止,减少信道浪费

冲突检测:

  • 有线局域网易于实现:测量信号强度,比较发送信号与接收信号强度
  • 无限局域网很难实现:接收信号强度淹没在本地发射信号强度

总结为边发边听,不发不听,每个主机发送数据帧时,监听信号强度,发送完成或不发送数据时,则不进行监听

最小的数据帧长度必须要满足L/R=2d/V=RTT,因为在传输时,可能会存在还未接收到检测冲突的报文就已经传输完成,就无法接收到冲突,就不能进行重传导致可靠性大大下降
image-20200207231347726

CSMA/CD效率

image-20200207231807632

效率远远大于Aloha协议

轮转MAC协议

信道划分MAC协议:

  • 网络负载很重时,共享信道效率高,且公平
  • 网络负载轻时,共享信道效率低

随机访问MAC协议:

  • 网络负载轻时,共享信道效率高,单个结点可以利用信道的全部带宽
  • 网络负载很重时,会产生冲突,造成时间的浪费,称为冲突开销

轮转访问MAC协议:

综合信道划分和随机访问的优点!

**轮询(polling)**做法:

  • 主结点轮流邀请从属结点发送数据,主结点一次只邀请一个结点,保障利用全部信道
  • 典型应用:"哑"从属设备,类似对讲机之类的

问题:

  • 轮询需要发送特殊的数据帧,需要占用信道带宽,产生轮询开销
  • 等待延迟
  • 单点故障风险,主结点一旦出问题,网络会瘫痪

令牌传递做法:

  • 控制令牌一次从一个结点传递到下一个结点
  • 令牌是一个特殊帧,当结点获得到令牌后才能发送数据,周而复始,不会造成冲突

问题:

  • 令牌传递有开销
  • 等待延迟
  • 单点故障,如果一个结点没有成功转发给下一个结点,网络上令牌就消失了,无法继续发送数据

MAC协议总结

信道划分MAC协议:时间,频带,码片划分

  • TDMA,FDMA,CDMA

随机访问MAC协议:

  • ALOHA,S-ALOHA,CSMA,CSMA/CD
  • CSMA/CD应用于以太网
  • CSMA/CA应用802.11无线局域网

轮转访问MAC协议:

  • 主结点轮询或令牌传递
  • 常用于蓝牙,FDDI