说明:该笔记是根据湖南科技大学高军老师的计算机网络课程
以及书籍:计算机网络 谢希仁主编
视频地址:https://www.icourse163.org/learn/HNKJ-1461816178?tid=1465255482
文章系列笔记:
三 数据链路层
3.1 数据链路层概述
- 数据链路层属于计算机网络的低层。数据链路层使用的信道主要有以下两种类型。
- 点对点信道。这种信道使用一对一的点对点通信方式。
- 广播信道。这种信道使用一对多的广播通信方式,因此过程比较复杂。广播信道上连接的主机很多,因此必须使用专用的共享信道协议来协调这些主机的数据发送。
- 链路(Link)就是从一个结点到相邻结点的一段物理线路,而中间没有任何其他的交换结点。
- 数据链路(Data Link)是指把实现通信协议的硬件和软件加到链路上,就构成了数据链路。
- 数据链路层以帧为单位传输和处理数据。
- 数据链路层把网络层交下来的数据构成帧发送到链路上,以及把接收到的帧中的数据取出并上交给网络层。在因特网中,网络层协议数据单元就是IP数据报(或简称为数据报、分组或包)。
3.2 点对点信道
3.2.1 通信过程
- 为了把主要精力放在点对点信道的数据链路层协议上,可以采用所示的三层模型。
- 结点A的数据链路层把网络层交下来的IP数据报添加首部和尾部封装成帧。
- 结点A把封装好的帧发送给结点B的数据链路层。
- 若结点B的数据链路层收到的帧无差错,则从收到的帧中提取出IP数据报上交给上面的网络层;否则丢弃这个帧。
3.3 基本问题
数据链路层协议有许多种,但有三个基本问题则是共同的。这三个基本问题是:封装成帧、透明传输和差错检测。
3.3.1 封装成帧
- 封装成帧(framing)就是在一段数据的前后分别添加首部和尾部,这样就构成了一个帧。
- 接收端在收到物理层上交的比特流后,就能根据首部和尾部的标记,从收到的比特流中识别帧的开始和结束。
- 网络层的IP数据报传送到数据链路层就成为帧的数据部分。在帧的数据部分的前面和后面分别添加上首部和尾部,构成了一个完整的帧。这样的帧就是数据链路层的数据传送单元。
- 一个帧的帧长等于帧的数据部分长度加上帧首部和帧尾部的长度。首部和尾部的一个重要作用就是进行帧定界(即确定帧的界限)。此外,首部和尾部还包括许多必要的控制信息。
- 每一种链路层协议都规定了所能传送的帧的数据部分长度上限——最大传送单元MTU (Maximum Transfer Unit)。
3.3.1.1 帧界定符
- 当数据是由可打印的ASCII码组成的文本文件时,帧定界可以使用特殊的帧定界符。
- 帧定界的概念,一个控制字符SOH (Start Of Header)放在一帧的最前面,表示帧的首部开始。
- 另一个控制字符EOT (End Of Transmission)表示帧的结束。请注意,SOH和EOT都是控制字符的名称。它们的十六进制编码分别是01(二进制是00000001)和04(二进制是00000100)。SOH(或EOT)并不是S,O,H(或E,O,T)三个字符。
- 使用了帧定界符,在接收端就知道前面收到的数据是个不完整的帧(只有首部开始符SOH而没有传输结束符EOT),必须丢弃。而后面收到的数据有明确的帧定界符(SOH和EOT),因此这是一个完整的帧,应当收下。
3.3.2 透明传输
- 由于帧的开始和结束的标记是使用专门指明的控制字符,因此,所传输的数据中的任何8比特的组合一定不允许和用作帧定界的控制字符的比特编码一样,否则就会出现帧定界的错误。
- 发送端的数据链路层在数据中出现控制字符SOH或EOT的前面插入一个转义字符ESC(其十六进制编码是1B,二进制是00011011)。
- 接收端的数据链路层在把数据送往网络层之前删除这个插入的转义字符。这种方法称为字节填充(byte stuffing)或字符填充(character stuffing)
3.3.3 差错检测
- 现实的通信链路都不会是理想的。这就是说,比特在传输过程中可能会产生差错:1可能会变成0,而0也可能变成1。这就叫做比特差错。
- 在一段时间内,传输错误的比特占所传输比特总数的比率称为误码率BER (Bit Error Rate)。
- 目前在数据链路层广泛使用了循环冗余检验
CRC (Cyclic Redundancy Check) 的检错技术。
3.3.3.1 奇偶校验
- 在待发送的数据后面添加1位奇偶校验位,使整个数据(包括所添加的校验位在内)中1的个数为奇数(奇校验)或偶数(偶校验)。
- 如果有奇数个位发生误码,则奇偶性发生变化,可以检查出误码。
- 如果有偶数个位发生误码,则奇偶性不发生变化,不能检查出误码(漏检)。
3.3.3.2 循环冗余检验
-
第一步:收发双方约定好一个生成多项式G(x); -
RC-16 = X16 +X15 + X2 + 1 -
CRC-CCITT = X16 +X12 + X5 + 1 -
CRC-32 = X32 +X26 + X23 + X22 + X16 +X12 + X11 +X10 + X8 +X7+ X5 +X4 + X2+ X + 1 -
第二步:发送方基于待发送的数据和生成多项式计算出差错检测码(冗余码),将其添加到待传输数据的后面一起传输。
- 第三步:接收方通过生成多项式来计算收到的数据是否产生了误码。
- CRC是一种检错方法,而FCS是添加在数据后面的冗余码,在检错方法上可以选用CRC,但也可不选用CRC。
- 在数据链路层若仅仅使用循环冗余检验CRC差错检测技术,则只能做到对帧的无差错接受,即:凡是接收端数据链路层接受的帧,我们都能以非常接近于 1的概率认为这些帧在传输过程中没有产生差错。
- 接收端丢弃的帧虽然曾收到了,但最终还是因为有差错被丢弃,即没有被接受。以上所述的可以近似地表述为(通常都是这样认为):凡是接收端数据链路层接受的帧均无差错。
3.3.3.3 案例
3.4 可靠传输
3.4.1 停止-等待协议(SW)
3.4.1.1 基本知识
- 停止等待就是每发送完一个分组就停止发送,等待对方的确认(ACK)。在收到确认(ACK)后再发送下一个分组。
- 接收方收不到数据分组,就不会发送
ACK 或NAK 。如果不采取其他措施,发送方就会一直处于等待接收方ACK 或NAK 的状态。 - 为解决该问题,可以在发送方发送完一个数据分组时,启动一个超时计时器。若到了超时计时器所设置的重传时间而发送方仍收不到接收方的任何
ACK 或NAK ,则重传原来的数据分组,这就叫做超时重传。 - 一般可将重传时间选为略大于从发送方到接收方的平均往返时间。
- 发送完一个分组后,必须暂时保留已发送的分组的副本(为发生超时重传时使用)。只有在收到相应的确认后才能清除暂时保留的分组副本。
- 分组和确认分组都必须进行编号(SEQ)。这样才能明确是哪一个发送出去的分组收到了确认,而哪一个分组还没有收到确认。
3.4.1.2 信道利用率
- 停止等待协议的优点是简单,但缺点是信道利用率太低。
3.4.2 回退N帧协议(GBN)(滑动窗口)
- 为了提高传输效率,发送方可以不使用低效率的停止等待协议,而是采用流水线传输。
- 流水线传输就是发送方可连续发送多个分组,不必每发完一个分组就停顿下来等待对方的确认。
- 这样可使信道上一直有数据不间断地在传送。显然,这种传输方式可以获得很高的信道利用率。
3.4.2.1 基本知识
- 1.采用3个比特给分组编序号,即序号0~7
- 2发送窗口的尺寸Wr的取值:1<W,<23- 1,本例取WT=5
- 3.接收窗口的尺寸WR的取值:WR=1
- 累计确认:接收方不一定要对收到的数据分组逐个发送确认,而是可以在收到几个数据分组后(由具体实现决定),对按序到达的最后一个数据分组发送确认。ACKn表示序号为n及以前的所有数据分组都已正确接收。
3.4.2.2 总结
3.4.3 选择重传协议
- 回退N帧协议的接收窗口尺寸WR只能等于1,因此接收方只能按序接收正确到达的数据分组
- 一个数据分组的误码就会导致其后续多个数据分组不能被接收方按序接收而丢弃(尽管它们无乱序和误码)。这必然会造成发送方对这些数据分组的超时重传,显然这是对通信资源的极大浪费。
- 为了进一步提高性能,可设法只重传出现误码的数据分组。因此,接收窗口的尺寸WR不应再等于1(而应大于1),以便接收方先收下失序到达但无误码并且序号落在接收窗口内的那些数据分组,等到所缺分组收齐后再一并送交上层。这就是选择重传协议。
- 选择重传协议为了使发送方仅重传出现差错的分组,接收方不能再采用累积确认,而需要对每个正确接收到的数据分组进行逐━确认!
3.5 信道复用技术
3.5.1 点对点协议PPP
- 在通信线路质量较差的年代,在数据链路层使用可靠传输协议曾经是一种好办法。因此,能实现可靠传输的高级数据链路控制
HDLC (High-level Data Link Control) 就成为当时比较流行的数据链路层协议。 - 对于点对点的链路,简单得多的点对点协议
PPP (Point-to-Point Protocol) 则是目前使用得最广泛的数据链路层协议。
组成
- PPP协议为在点对点链路传输各种协议数据报提供了一个标准方法,主要由以下三部分构成:
- 对各种协议数据报的封装方法((封装成帧)
- 链路控制协议LCP,用于建立、配置以及测试数据链路的连接
- 一套网络控制协议NCPs其中的每一个协议支持不同的网络层协议
帧格式
- 首部的第一个字段和尾部的第二个字段都是标志字段F (Flag),规定为0x7E(符号“0x”表示它后面的字符是用十六进制表示的。十六进制的7E的二进制表示是01111110)。标志字段表示一个帧的开始或结束。因此标志字段就是PPP帧的定界符。
- 首部中的地址字段A规定为0xFF(即11111111),控制字段C规定为0x03(即00000011)。最初曾考虑以后再对这两个字段的值进行其他定义,但至今也没有给出。可见这两个字段实际上并没有携带PPP帧的信息。
- PPP首部的第四个字段是2字节的协议字段。当协议字段为0x0021时,PPP帧的信息字段就是IP数据报。若为0xC021,则信息字段是PPP链路控制协议LCP的数据,而0x8021表示这是网络层的控制数据。
- 信息字段的长度是可变的,不超过1 500字节。
- 尾部中的第一个字段(2字节)是使用CRC的帧检验序列FCS。
字节填充:请查看前面的透明传输知识
差错校验:请查看前面的差错校验知识
PPP协议的工作状态
- 当用户PC通过调制解调器呼叫路由器时(通常是在屏幕上用鼠标点击一个连接按钮),路由器就能够检测到调制解调器发出的载波信号。
- 在双方建立了物理层连接后,PPP就进入链路建立(Link Establish)状态,其目的是建立链路层的LCP连接。
- 这时LCP开始协商一些配置选项,即发送LCP的配置请求帧(Configure-Request)。这是个PPP帧,其协议字段置为LCP对应的代码,而信息字段包含特定的配置请求。
- (1) 配置确认帧(Configure-Ack):所有选项都接受。
- (2) 配置否认帧(Configure-Nak):所有选项都理解但不能接受。
- (3) 配置拒绝帧(Configure-Reject):选项有的无法识别或不能接受,需要协商。
- LCP配置选项包括链路上的最大帧长、所使用的鉴别协议(authenticationprotocol)的规约(如果有的话),以及不使用PPP帧中的地址和控制字段(因为这两个字段的值是固定的,没有任何信息量,可以在PPP帧的首部中省略这两个字节)。
- 协商结束后双方就建立了LCP链路,接着就进入鉴别(Authenticate)状态。在这一状态,只允许传送LCP协议的分组、鉴别协议的分组以及监测链路质量的分组。
- 在网络层协议状态,PPP链路的两端的网络控制协议NCP根据网络层的不同协议互相交换网络层特定的网络控制分组。
- 如果在PPP链路上运行的是IP协议,则对PPP链路的每一端配置IP协议模块(如分配IP地址)时就要使用NCP中支持IP的协议——IP控制协议IPCP (IP ControlProtocol)。
- 当网络层配置完毕后,链路就进入可进行数据通信的“链路打开”(Link Open)状态。链路的两个PPP端点可以彼此向对方发送分组。两个PPP端点还可发送回送请求LCP分组(Echo-Request)和回送回答LCP分组(Echo-Reply),以检查链路的状态。
- 数据传输结束后,可以由链路的一端发出终止请求 LCP分组(Terminate-Request)请求终止链路连接,在收到对方发来的终止确认 LCP分组(Terminate-Ack)后,转到链路终止状态。如果链路出现故障,也会从链路打开状态转到链路终止状态。当调制解调器的载波停止后,则回到“链路静止”状态。
3.5.2 信道复用技术
共享信道要着重考虑的一个问题就是如何使众多用户能够合理而方便地共享通信媒体资源。这在技术上有两种方法:
- (1) 静态划分信道,频分复用、时分复用、波分复用和码分复用等。用户只要分配到了信道就不会和其他用户发生冲突。但这种划分信道的方法代价较高,不适合于局域网使用。
- (2) 动态媒体接入控制,它又称为多点接入(multiple access),其特点是信道并非在用户通信时固定分配给用户。这里又分为以下两类:● 随机接入 随机接入的特点是所有的用户可随机地发送信息。但如果恰巧有两个或更多的用户在同一时刻发送信息,那么在共享媒体上就要产生碰撞(即发生了冲突),使得这些用户的发送都失败。因此,必须有解决碰撞的网络协议。● 受控接入 受控接入的特点是用户不能随机地发送信息而必须服从一定的控制。这类的典型代表有分散控制的令牌环局域网和集中控制的多点线路探询(polling),或称为轮询。
频分复用与时分复用
- 频分复用的所有用户在同样的时间占用不同的带宽资源(请注意,这里的带宽是频率带宽而不是数据的发送速率)。而时分复用则是将时间划分为一段段等长的时分复用帧(TDM帧)。
- 时分复用的所有用户是在不同的时间占用同样的频带宽度。这两种复用方法的优点是技术比较成熟,但缺点是不够灵活。时分复用则更有利于数字信号的传输。
- 在进行通信时,复用器(multiplexer)总是和分用器(demultiplexer)成对地使用。在复用器和分用器之间是用户共享的高速信道。分用器的作用正好和复用器的作用相反,它把高速信道传送过来的数据进行分用,分别送交到相应的用户。
波分复用
- 波分复用
WDM (Wavelength Division Multiplexing) 就是光的频分复用。光纤技术的应用使得数据的传输速率空前提高。
- 光信号传输了一段距离后就会衰减,因此对衰减了的光信号必须进行放大才能继续传输。现在已经有了很好的掺铒光纤放大器
EDFA (Erbium DopedFiber Amplifier) 。它是一种光放大器,不需要像以前那样复杂,先把光信号转换成电信号,经过电放大器放大后,再转换成为光信号。
3.5.3 码分复用(重点)
- 码分复用
CDM 是另一种共享信道的方法。实际上,由于该技术主要用于多址接入,人们更常用的名词是码分多址CDMA(Code Division Multiple Access) 。 - 同理,频分复用
FDM 和时分复用TDM 同样可用于多址接入,相应的名词是频分多址FDMA(Frequency Division Multiple Access) 和时分多址TDMA(Time Division Multiple 锉零课程中,我们不严格区分复用与多址的概念。 - 复用是将单一媒体的频带资源划分成很多子信道,这些子信道之间相互独立,互不干扰。从媒体的整体频带资源上看,每个子信道只占用该媒体频带资源的一部分。
- 多址(更确切地应该称为多点接入)处理的是动态分配信道给用户。这在用户仅仅暂时性地占用信道的应用中是必须的,而所有的移动通信系统基本上都属于这种情况。相反,在信道永久性地分配给用户的应用中,多址是不需要的(对于无线广播或电视广播站就是这样)。
- 某种程度上,
FDMA、TDMA、CDMA 可以分别看成是FDM、TDM、CDM 的应用。 - 与
FDM 和TDM 不同,CDM 的每一个用户可以在同样的时间使用同样的频带进行通信。 - 由于各用户使用经过特殊挑选的不同码型,因此各用户之间不会造成干扰。
CDM 最初是用于军事通信的,因为这种系统所发送的信号有很强的抗干扰能力,其频谱类似于白噪声,不易被敌人发现。- 随着技术的进步,
CDMA 设备的价格和体积都大幅度下降,因而现在已广泛用于民用的移动通信中。
3.5.3.1 码片序列
-
在CDMA 中,每一个比特时间再划分为 m个短的间隔,称为码片(chip)。通常 m的值是64或128。 -
使用CDMA 的每一个站被指派一个唯一的mbit 码片序列(chip sequence) 。一个站如果要发送比特1,则发送它自己的mbit 码片序列。如果要发送比特0,则发送该码片序列的二进制反码。 -
例如,指派给S站的8bit 码片序列是00011011 。当S发送比特1时,它就发送序列00011011 ,而当S发送比特0时,就发送11100100。为了方便,我们按惯例将码片中的0写为-1,将1写为+1。因此S站的码片序列是(-1 -1-1 +1 +1 -1 +1 +1)。 -
CDMA 系统的一个重要特点就是这种体制给每一个站分配的码片序列不仅必须各不相同,并且还必须互相正交(orthogonal)。在实用的系统中是使用伪随机码序列。 -
用数学公式可以很清楚地表示码片序列的这种正交关系。令向量 S表示站S的码片向量,再令 T表示其他任何站的码片向量。
- 向量S为(-1 -1 -1 +1 +1 -1 +1 +1),同时设向量T为(-1 -1 +1 -1 +1 +1+1 -1),这相当于T站的码片序列为00101110。将向量S和T的各分量值代入(2-3)式就可看出这两个码片序列是正交的。不仅如此,向量S和各站码片反码的向量的内积也是0。
3.6 CSMA/CD协议
- 多点接入:就是说明这是总线型网络,许多计算机以多点接入的方式连接在一根总线上。协议的实质是载波监听和碰撞检测。
- 载波监听:就是用电子技术检测总线上有没有其他计算机也在发送。其实总线上并没有什么载波,这里只不过借用一下载波这个名词而已。因此载波监听就是检测信道,这是个很重要的措施。不管在发送前,还是在发送中,每个站都必须不停地检测信道。
- 碰撞检测:也就是边发送边监听,即适配器边发送数据边检测信道上的信号电压的变化情况,以便判断自己在发送数据时其他站是否也在发送数据。
- 使用
CSMA/CD 协议时,一个站不可能同时进行发送和接收(但必须边发送边监听信道)。因此使用CSMA/CD 协议的以太网不可能进行全双工通信而只能进行双向交替通信(半双工通信)。
重要时刻
- 在t = 0时,A发送数据。B检测到信道为空闲。
- 在t = τ - δ 时(这里τ > δ > 0),A发送的数据还没有到达B时,由于B检测到信道是空闲,因此B发送数据。
- 经过时间δ / 2后,即在t = τ - δ / 2时,A发送的数据和B发送的数据发生了碰撞。但这时A和B都不知道发生了碰撞。在t = τ 时,B检测到发生了碰撞,于是停止发送数据。
- 在t = 2τ - δ 时,A也检测到发生了碰撞,因而也停止发送数据。
- 由此可见,每一个站在自己发送数据之后的一小段时间内,存在着遭遇碰撞的可能性。
- 最先发送数据帧的A站,在发送数据帧后至多经过时间2τ就可知道所发送的数据帧是否遭受了碰撞。这就是δ →0的情况。因此以太网的端到端往返时间2τ称为争用期(contention period),它是一个很重要的参数。
- 争用期又称为碰撞窗口(collision window)。这是因为一个站在发送完数据后,只有通过争用期的“考验”,即经过争用期这段时间还没有检测到碰撞,才能肯定这次发送不会发生碰撞。
截断二进制指数退避法
- 以太网使用截断二进制指数退避
(truncated binary exponential backoff) 算法来确定碰撞后重传的时机。截断二进制指数退避算法并不复杂。这种算法让发生碰撞的站在停止发送数据后,不是等待信道变为空闲后就立即再发送数据,而是推迟(这叫作退避)一个随机的时间。 - 当重传达16次仍不能成功时,表明同时打算发送帧的主机太多,以至于连续发生碰撞,则丢弃该帧,并向高层报告。
- 若连续多次发生碰撞,就表明可能有较多的主机参与竞争信道。但使用上述退避算法可使重传需要推迟的平均时间随重传次数而增大(这也称为动态退避),因而减小发生碰撞的概率,有利于整个系统的稳定。
信道利用率
-
发送方 -
接收方
3.7 CAMA/CA协议
为什么?
- 既然
CSMA/CD 协议已经成功地应用于使用广播信道的有线局域网,那么同样使用广播信道的无线局域网能不能也使用CSMA/CD 协议呢? - 在无线局域网中,仍然可以使用载波监听多址接入
CSMA ,即在发送帧之前先对传输媒体进行载波监听。若发现有其他站在发送帧,就推迟发送以免发生碰撞。 - 由于无线信道的传输条件特殊,其信号强度的动态范围非常大,无线网卡上接收到的信号,强度往往会远远小于发送信号的强度(可能相差百万倍),如果要在无线网卡上实现碰撞,检测CD,对硬件的要求非常高。
- 即使能够在硬件上实现无线局域网的碰撞检测功能,但由于无线电波传播的特殊性(存在隐蔽站问题),进行碰撞检测的意义也不大。
802.11无线局域网使用CSMA/CA协议
-
802.11无线局域网使用CSMA/CA协议,在CSMA的基础上增加了一个碰撞避免CA功能,而不再实现碰撞检测功能。 -
由于不可能避免所有的碰撞,并且无线信道误码率较高,802.11标准还使用了数据链路层,确认机制(停止-等待协议)来保证数据被正确接收。 -
分布式协调功能DCF(Distributed Coordination Function) 。在DCF 方式下,没有中心控制站点,每个站点使用CSMA/CA协议 通过争用信道来获取发送权,这是802.11定义的默认方式。 -
点协调功能PCF(Point Coordination Function) 。PCF 方式使用集中控制的接入算法(一般在接入点AP实现集中控制),是802.11定义的可选方式,在实际中较少使用。 -
802.11标准规定,所有的站点必须在持续检测到信道空闲一段指定时间后才能发送帧,这段时间称为帧间间隔IFS. -
帧间间隔的长短取决于该站点要发送的帧的类型:高优先级帧需要等待的时间较短,因此可优先获得发送权; -
低优先级帧需要等待的时间较长。 -
若某个站的低优先级帧还没来得及发送,而其他站的高优先级帧已发送到信道上,则信道变为忙态,因而低优先级帧就只能再推迟发送了。这样就减少了发生碰撞的机会。常用的两种帧间间隔如下: -
短帧间间隔SIFS(28us),是最短的帧间间隔,用来分隔开属于一次对话的各帧。一个站点应当能够在这段时间内从发送方式切换到接收方式。使用SIFS的帧类型有ACK帧、CTS帧、由过长的MAC帧分片后的数据帧、以及所有回答AP探询的帧和在PCF方式中接入点AP发送出的任何帧。 -
DCF帧间间隔DIFS(128us),它比短帧间间隔SIFS要长得多,在DCF方式中用来发送数据帧和管理帧。
原理
退避算法
|