MENU

数据链路层(一)

October 29, 2018 • Read: 230 • 计算机网络

数据发送模型

数据链路和帧

链路(Link)是指的从一个节点到相邻节点的一段物理线路(有线或无线),而中间没有任何其他的交换节点。

数据链路(Data Link)则是另一个概念,这是因为当需要在一条线路上传送数据时,除了必须有一条物理线路外,还必须有一些必要的通信协议来控制这些数据的传输。

数据链路层把网络层交下来的数据封装成帧发送到链路上,以及把接收到的帧中的数据取出并上交给网络层。在因特网中,网络层协议数据单元就是IP数据报(或简称为数据报、分组或包)。数据链路层封装的帧,在物理层变成数字信号在链路上传输。

数据链路层的三个基本问题

封装成帧

封装成帧,将网络层的IP数据报的前后分别添加首部和尾部,就构成了一个帧。

每一种数据链路层协议都规定了所能够传送的帧的数据部分长度的上限--即最大传输单元MTU(Maximum Transfer Unit),以太网的MTU为1500个字节。

帧的首部和尾部有帧开始符和帧结束符,称为帧定界符。接收端收到物理层传过来的数字信号读取到帧开始字符一直到帧结束字符,才认为接收到了一个完整的帧。

透明传输

若传输的数据是ASCII中“可打印字符(共95个)”集时,一般不会出现问题,若传输的数据不是仅由“可打印字符”组成时,就会出现问题,如下图:

解决办法是用字节填充法。发送端的数据链路层在数据中出现控制字符”SOH“或”EOT“的前面插入一个字符“ESC”(其十六进制编码是1B)

字节填充(byte stuffing)或“字符填充”(character stffing)——接收端的数据链路层在将数据送往网络层之前删除插入的转义字符

如果转义字符也出现在数据当中,那么应在转义字符前插入一个转义字符。当接收端收到连续的两个转义字符时,就删除其中前面的一个。

差错控制

现实的通信链路都不会是理想的。这就是说,比特在传输过程中可能会产生差错:1可能会变成0,而0也可能变成1,这就叫做比特差错。

为了保证数据传输的可靠性,在计算机网络传输数据时,必须采用各种差错检测措施。目前在数据链路层广泛使用了循环冗余检验CRC(Cyclic Redundancy Check)的差错检验技术。

CRC运算示例


传送的二进制数据为101001,在其末位添加n位0,这里n=3,添加了三个0,然后除以n+1位的随机数,这里4位的随机二进制数选择的是1101(任何都行,只要是n+1位二进制数)

CRC做的除法和我们一般意义上的除法不同。首先看1010和1101,因为高位都是1,所以直接商1(跟两数的大小无关,只与最高位有关),之后也不是常规意义上将1010和1101做差,而是将其做异或,高位相同为0就不写,异或结果为111,然后将后面的0落下来变成1110,继续做除法。

因为1110和1101高位都是1,所以直接商1,然后做异或运算,高位相同为0直接不写,就变成011,将后面的1落下来变成0111,继续做除法。

因为0111的高位是0,1101高位是1,所以商0,然后进行异或运算,高位相同为0直接不写,就变成111,将后面的0落下来变成1110,继续做除法。

因为1110和1101高位都是1,所以商1,然后做异或运算,高位相同为0直接不写,就变成011,将后面的0落下来就变成0110,继续做除法。

因为0110的高位是0,1101的高位是1,所以商0,然后做异或运算,高位相同为0直接不写,就变成110,将后面的0落下来就变成1100,继续做除法。

因为1100和1101的高位相同都是1,所以商1,然后做异或运算,高位相同为0直接不写,就变成001,此时后面已经没有数据为落下来了,运算结束。

我们看整个运算结束后,什么数据是为我们所用的。首先,余数(FCS)是有用的,FCS称为帧检验序列,添加在数据后面,即整个二进制数据变为101001001(之前的000只是为了计算用的,这里就不再需要了,直接用FCS替换)。再有就是随机选择的除数也是有用的,在传输过程中会再次利用101001001÷1101,如果得到的结果不是0000,则说明传输过程中出错。这里可以直接利用相同的运算方法计算一下101001001÷1101,看是不是0000

数据链路层只负责没有差错的接收,如果出错就直接丢掉。比如一台计算机正在从一台服务器上下载文件,服务器传输数据的过程中会经过很多结点将数据转发到计算机上,如果中途某两个结点转发数据的过程中出现错误,这两个结点中接收方结点的数据链路层就会将该数据丢掉,此时发生丢包,丢包以后,数据链路层是不负责告知服务器重新传输某个数据包的,而是由计算机告知服务器重新传输数据包

还有可能发生这种情况,即数据错误了,但是数据链路层在进行CRC校验的时候,检验结果是正确的,所以数据链路层认为是正确的,这也是有可能的。一般来说,除数长度越小,发生误判的概率越大。以十进制除法来举例,假如除数为2,那么余数只有可能是0或者1,但是如果除数是100,那么余数可能是0-99,余数种类越小,出现误判的概率越大。

两种情况下的数据链路层

点到点信道(PPP协议)

点到点信道是指的一条链路上就一个发送端和接收端的信道,通常用在广域网链路。

PPP协议的特点
  • 简单(不提供可靠传输)
  • 封装成帧(首部 尾部,帧开始符 帧结束符)
  • 透明传输(加转义字符,收到后去掉转义字符)
  • 差错检验(CRC计算FCS)
  • 支持多种网络层协议(IPV4和IPV6都可以封装到PPP帧中)
  • 多种类型链路(光纤、铜线,同步、异步,串行、并行均可)
  • 检测连接状态
  • 最大传送单元(1500字节)
  • 网络层地址协商(能够为拨号的一端分配IP地址,子网掩码 网关和DNS)
  • 数据压缩协商(数据压缩技术)
PPP协议的组成

PPP协议有三个组成部分
i2OjUA.png

PPP协议帧格式

iRSJcq.png
在上图PPP帧的首部中有一个占用2字节的协议,这个协议的内容是标识后面的信息部分是什么,具体来说分以下几种:

  • 0x0021——PPP帧的信息字段是IP数据报
  • 0xC021——信息字段是PPP链路控制数据
  • 0x8021——表示这时网络控制数据
  • 0xC023——信息字段是安全认证PAP
  • 0xC025——信息字段是LQR
  • 0xC223——信息字段是安全性认证CHAP

可以抓包查看PPP帧首部
iRS44H.png

异步传输使用字节填充

在异步传输的链路上,数据传输以字节为单位,PPP帧的转义符定义为0x7D,并使用字节填充

把信息字段中出现的每一个0x7E字节转变成为2字节序列(0x7D,0x5E)

若信息字段中出现一个0x7D的字节(即出现了和转义字符一样的比特组合),则把0x7D转变成为2字节序列(0x7D,0x5D)
iRS7vt.png

同步使用零比特填充

在同步传输的链路上,数据传输以帧为单位,PPP协议采用零比特填充方法来实现透明传输。如果把PPP协议帧界定符0x7E写成二进制01111110,可以看到中间有连续的6个1,只要想办法在数据部分不要出现连续的6个1,就肯定不会出现这界定符。具体办法就是“零比特填充法”。
iRktJS.png

广播信道的局域网

iREk4K.png
使用集线器组建的局域网也是广播信道,是总线型拓扑
iREZge.png

以太网标准

以太网(Ethernet)是一种计算机局域网组网技术。IEEE制定的IEEE 802.3标准给出了以太网的技术标准,即以太网的介质访问控制协议(CSMA/CD)及物理层技术规范(包括物理层的连线、电信号和介质访问层协议的内容)

在IEEE 802.3标准中,为不同的传输介质制定了不同的物理层标准,在这些标准中前面的数字表示传输速度,单位是“Mbps”,最后的一个数字表示单段网线长度(基准单位是100m),Base表示“基带”的意思。
iREKHI.png

CSMA/CD协议

CSMA/CD表示Carrier Sense Multiple Access with Collision Detection(载波监听多点接入/碰撞检测)

“多点接入”表示许多计算机以多点接入的方式连接在一根总线上。

“载波监听”是指每一个站在发送数据之前先要检测一下总线上是否有其他计算机在发送数据,如果有,则暂时不要发送数据,以免发生碰撞。

比如,A计算机发送的信号和B计算机发送的信号在链路C处发生碰撞,碰撞后的信号相互叠加,在总线上电压变化幅度将会增加,发送方检测到电压变化超过一定的门限值时,就认为发生冲突,这就是碰撞检测
iReNKe.png

以太网最短帧

为了能够检测到正在发送的帧在总线上是否产生冲突,以太网的帧不能太短,如果太短就有可能检测不到自己发送的帧产生了冲突。
iRmnRf.png
假设A传输数据到B的时间是$\tau$,并且如果产生冲突,传输的数据会返回A,告诉A发生冲突了,那么最大的产生冲突的时间就是$2\tau$。即传输过去的数据刚好到B的瞬间,B也向A发送了一个数据,此时两个数据就产生冲突。

以太网设计最大端到端长度为5km(实际上的以太网覆盖范围远远没有这么大),单程传播时延为大约为25.6μs,往返传播时延为51.2μs,10M标准以太网最小帧为:
$$
10Mb/s\times 51.2μs =107b/s\times 51.2×10^{-6}s=512b
$$
512比特也就是64字节,这就意味着以太网发送数据帧如果前64字节没有检测出冲突,后面发送的数据就一定不会发生冲突。换句话说,如果发生碰撞,就一定在发送前64字节之内。由于一旦检测出冲突就立即终止发送,这时发送的数据一定小于64字节,因此凡是长度小于64字节的帧都是由于冲突而异常终止的无效帧,只要收到了这种无效帧,就应当立即将其终止。

冲突解决方法——退避算法

总线型网络中的计算机数量越多,在链路上发送数据产生冲突机会就多。

以太网使用截断二进制指数退避(truncated binary exponential backoff)算法来解决碰撞问题。算法流程如下:

  • 确定基本退避时间,它就是争用期2τ。以太网把争用期定为51.2μs。对于10Mb/s以太网,在争用期内可发送512bit,即64字节。也可以说争用期是512比特时间。1比特时间就是发送1比特所需的时间。
  • 从离散的整数集合[0,1,…,($2^{k-1}$)]中随机取出一个数,记为$r$。重传应推后的时间就是r倍的争用期。上面的参数$k$按下面的公式计算:

$$
k = Min(重传次数,10)
$$

  • 当重传达16次仍不能成功时(这表明同时打算发送数据的站太多,以致连续发生冲突),则丢弃该帧,并向高层报告。

这个算法还是比较好理解的,举个例子,假设有两台计算机要通信,在第一次传数据的过程中发生冲突了,那么此时$k=1$,从集合[0,1]中随机取一个数,推后该数乘以51.2μs。第二次失败也一样,依次类推。

以太网帧格式

常用的以太网MAC帧格式有两种标准,一种是EthernetV2标准(即以太网V2标准),另一种是IEEE的802.3标准。使用得最多的是以太网V2的MAC帧格式。

Ethernet II的帧比较简单,由五个字段组成

当数据字段的长度小于46字节时,数据链路层就会在数据字段的后面加入一个整数字节的填充字段,以保证以太网的MAC帧长不小于64字节,接收端还必须能够将添加的字节去掉。

IEEE802.3标准规定凡出现下列情况之一的即为无效的MAC帧:

  • 帧的长度不是整数个字节
  • 用收到的帧检验序列FCS查出有差错
  • 收到的帧的MAC客户数据字段的长度不在46-1500字节之间。考虑到MAC帧首部和尾部的长度共有18字节,可以得出有效的MAC帧长度为64-1518字节之间

对于检查出的无效MAC帧就简单地丢弃。以太网不负责重传丢弃的帧。

以太网信道利用率

设帧长为$L(bit)$,数据发送率为$C(bit/s)$,所以帧的发送时间为$L/C=T_0(s)$

利用率是指的发送数据的时间占整个时间的比例。如下图所示,平均发送一帧所需要的时间经历了n倍争用期$2\tau$,$T_0$为发送该帧所需时间,$\tau$为该帧传播时延。

有冲突时信道利用率为
$$
S=\frac{T_0}{n2\tau +T_0+\tau}
$$
从公式可以看出,要想提高信道利用率最好是n=0,这就意味着以太网上的各个计算机发送数据不会产生碰撞(这显然已经不是CSMA/CD,而需要一种特殊的调度方法),并且能够非常有效的利用网络的传输资源,即总线一旦空闲就有一个站立即发送数据。这种情况算出来的信道利用率是极限信道利用率。
$$
S_{max}=\frac{T_0}{T_0+\tau}=\frac{1}{1+\frac{\tau}{T_0}}
$$
要想提高极限信道利用率就要降低公式中的$\frac{\tau}{T_0}$

降低上面的分式有两种办法,分子足够小或者分母足够大,首先说分子,$\tau$值和以太网连线的长度有关,这就意味着$\tau$值要小,以太网网线的长度就不能太长。其次是分母,带宽一定的情况下$T_0$和帧的长度有关,这就意味着,以太网的帧不能太短。

MAC地址

为了在广播信道实现点到点通信,就需要网络中的每个网卡有一个地址。这个地址称为物理地址或MAC地址(因为这种地址用在MAC帧中)。IEEE802标准为局域网规定了一种48位二进制的全球地址。

这种6字节的MAC地址已被固化在网卡的ROM中。因此,MAC地址也叫作硬件地址(hardware address)或物理地址。当这块网卡插入(或嵌入)到某台计算机后,网卡上的MAC地址就成为这台计算机的MAC地址了。

前24位二进制表示的是厂家信息,后24位是厂家给的编号。所以要想生产网卡必须去专门的机构进行注册,否则就可能会发生MAC地址冲突的问题。

那么MAC地址是否可以更改呢?答案是肯定的,只不过我们更改的并不是真正网卡上的MAC地址,这个已经被写死了,无法更改,但是我们可以给计算机指定一个值,让计算机使用我们指定的这个值,不使用网卡的MAC地址(MAc地址冲突也无法正常上网)

网卡有过滤功能,适配器从网络上每收到一个MAC帧就先用硬件检查MAC帧中的目的地址。如果是发往本站的帧则收下,然后再进行其他的处理。否则就将此帧丢弃,不再进行其他的处理。这样做就不浪费主机的处理机和内存资源。这里“发往本站的帧”包括以下三种帧:

  1. 单播(unicast)帧(一对一),即收到的帧的MAC地址与本站的硬件地址相同
  2. 广播(broadcast)帧(一对全体),即发送给本局域网上所有站点的帧(全1地址)
  3. 多播(multicast)帧(一对多),即发送给本局域网上一部分站点的帧
Archives Tip
QR Code for this page
Tipping QR Code
Leave a Comment