第三章数据链路层

3.1 数据链路层的功能

加强物理层传输原始比特流的功能,将物理层提供的可能出错的物理连接改造为逻辑上无差错的数据链路,使之对网络层表现为一条无差错的链路。下面具体介绍数据链路层的功能。
3.1.1为网络层提供服务

无确认的无连接服务

源机器发送数据帧时不需先建立链路连接,目的机器收到数据帧时不需发回确认。
对丢失的帧,数据链路层不负责重发而交给上层处理。
适用于实时通信或误码率较低的通信信道,如以太网。

有确认的无连接服务

源机器发送数据帧时不需先建立链路连接,但目的机器收到数据帧时必须发回确认。
源机器在所规定的时间内未收到确定信号时,就重传丢失的帧,以提高传输的可靠性。
该服务适用于误码率较高的通信信道,如无线通信。

有确认的面向连接服务

帧传输过程分为三个阶段:建立数据链路、传输帧、释放数据链路。
目的机器对收到的每一帧都要给出确认,源机器收到确认后オ能发送下一帧,因而该服务的可靠性最高。
该服务适用于通信要求(可靠性、实时性)较高的场合。

有连接就一定要有确认,即不存在无确认的面向连接的服务。

3.1.2链路管理

数据链路层连接的建立、维持和释放过程称为链路管理,它主要用于面向连接的服务。
过程

首先确认对方已处于就绪状态,
并交换一些必要的信息以对帧序号初始化,
建立连接,在传输过程中则要能维持连接,
传输完毕后要释放该连接。

在多个站点共享同一物理信道的情况下(例如在局域网中)如何在要求通信的站点间分配和管理信道也属于数据链路层管理的范畴。

3.1.3帧定界、帧同步与透明传输

两个工作站之间传输信息时,必须将网络层的分组封装成帧,以帧的格式进行传送
将一段数据的前后分别添加首部和尾部,就构成了帧。

帧定界。

首部和尾部中含有很多控制信息,它们的一个重要作用是确定帧的界限,即帧定界。

帧同步

帧同步指的是接收方应能从接收到的二进制比特流中区分出帧的起始与终止。

透明传输

采取有效的措施解决误认为“传输结東”而丢弃后面的数据的问题,即透明传输。不管所传数据是什么样的比特组合,都应当能在链路上传送。

3.1.4流量控制

流量控制实际上就是限制发送方的数据流量,使其发送速率不超过接收方的接收能力。
通过某种反馈机制使发送方能够知道接收方是否能跟上自己,即需要有一些规则使得发送方知道在什么情况下可以接着发送下一帧,而在什么情况下必须暂停发送,以等待收到某种反馈信息后继续发送。
并不是数据链路层特有的功能

对于数据链路层来说,控制的是相邻两结点之间数据链路上的流量,
对于运输层来说,控制的则是从源端到目的端之间的流量。

3.1.5差错控制

用以使发送方确定接收方是否正确收到由其发送的数据的方法称为差错控制。
通常,这些错误可分为位错和帧错。

位错

位错指帧中某些位出现了差错。

通常采用循环冗余校验(CRC)方式发现位错,通过自动重传请求( Automatic Repeat request,ARQ)方式来重传出错的幀。

ARQ法只需返回很少的控制信息就可有效地确认所发数据帧是否被正确接收。

帧错

帧错指帧的丢失、重复或失序等错误。
在数据链路层引入定时器和编号机制,能保证每一帧最终都能有且仅有一次正确地交付给目的结点。

3.2 组帧

目的

为了在出错时只重发出错的帧,而不必重发全部数据,从而提高效率。
为了使接收方能正确地接收并检查所传输的帧,发送方必须依据一定的规则把网络层递交的分组封装成帧(称为组帧)。

解决的问题

帧定界

组帧时既要加首部,又要加尾部。原因是,在网络中信息是以帧为最小单位进行传输的,所以接收端要正确地接收帧,必须要清楚该帧在一串比特流中从哪里开始到哪里结束(因为接收端收到的是一串比特流,没有首部和尾部是不能正确区分帧的)。而分组(即IP数据报)仅是包含在帧中的数据部分(后面将详细讲解),所以不需要加尾部来定界。

帧同步
透明传输

四种方法

3.2.1 字符计数法

在帧头部使用一个计数字段来标明帧内字符数。
缺点

如果计数字段出错,即失去了帧边界划分的依据,那么接收方就无法判断所传输帧的结束位和下一帧的开始位,收发双方将失去同步,从而造成灾难性后果。

3.2.2 字符填充的首尾定界符法

使用一些特定的字符来定界一帧的开始(DLE STX)与结束(DLEETX)。
在特殊字符前面填充一个转义字符 (DLE)来加以区分

3.2.3 零比特填充的首尾标志法

使用一个特定的比特模式,即01111110来标志一帧的开始和结束。
发送方的数据链路层在信息位中遇到5 个连续的“广时,将自动在其后插入一个“0七而接收方做该过程的逆操作,即每收到5个连续的“1"时,自动删除后面紧跟的“0七以恢复原信息。
零比特填充法很容易由硬件来实现,性能优于字符填充法。

324违规编码法

物理层进行比特编码时,通常采用违规编码法。
借用这些违规编码序列来定界帧的起始和终止。
局域网IEEE 802标准就采用了这种方法。
只适用于采用冗余编码的特殊编码环境。

目前较常用的组帧方法是比特填充法和违规编码法

3.3 差错控制

影响因素：信道固有噪声干扰

解决方法：提高信噪比

外界的冲击噪声是产生差错的重要原因

没有办法通过提高信号幅度来降低干扰

利用编码技术

自动重传请求ARQ

接收端检测出差错时,就设法通知发送端重发,直到接收到正确的码字为止。

前向纠错FEC

接收端不但能发现差错,而且能确定比特串的错误位置,从而加以纠正。

3.3.1 检错编码

检错编码都采用冗余编码技术

附加一定的冗余位,构成一个符合某一规则的码字后再发送。当要发送的有效数据变化时,相应的冗余位也随之变化,使得码字遵从不变的规则。接收端根据收到的码字是否仍符合原规则来判断是否出错。

奇偶校验码

由 n-1 位信息元和 1 位校验元组成

奇校验码

奇校验码,那么在附加一个校验元后,码长为n的码字中“1”的个数为奇数;

偶校验码

偶校验码,那么在附加一个校验元以后,码长为n的码字中“1”的个数为偶数。

循环冗余码

又称多项式码

任何一个由二进制数位串组成的代码都可以与一个只含有0和1两个系数的多项式建立一一对应关系。

如: 1110011有7位,表示成多项式是 X^6+X^5+X^4+X+1,而多项式 X^5+X^4+X^2+X 对应的位串是 11011

给定一个 m bit的帧或报文,发送器生成一个 r bit 的序列,称为帧检验序列(FCS)

运算过程

发送方和接收方事先商定一个多项式G(x)(最高位和最低位必须为1)
帧有m位,其对应的多项式为M(x)
加0。假设G(x)的阶为 r,在帧的低位端加上 r 个0。
模2除。利用模2除法,用G(x)对应的数据串去除上一步计算出的数据串,得到的余数即为冗余码(共 r 位,前面的0不可省略)。

以2为模运算，刚好是异或操作。

计算举例:

设G(x) = 1101 (即 r = 3）
传送数据 M = 101001 (即 m= 6
被除数一共 m+r 位：101001 + 000
经模2 除法运算后的结果是:商0=110101 (这个商没什么用),余数 R = 001。
送出去的数据为 101001 001 (即 2^r * W + FCS),共有m + r位。

3.3.2 纠错编码

解决差错问题的一种方法是在每个要发送的数据块上附加足够的冗余信息,使接收方能够推导出发送方实际送出的应该是什么样的比特串。
海明码

原理

在有效信息位中加入几个校验位形成海明码,并把海明码的每个二进制位分配到几个奇偶校验组中。
当某一位出错后,就会引起有关的几个校验位的值发生变化,这不但可以发现错位,而且能指出错位的位置,为自动纠错提供依据。

计算步骤 (1) 确定海明码的位数 - 设 n 为有效信息的位数,k 为校验位的位数,则信息位 n 和校验位 k 应满足 n+k < 2^k - 1 (若要检测两位错,则需再增加1位校验位,即 k+1 位) (2) 确定校验位的分布 - 规定校验位 Pi 在海明位号为 2^(i-1) 的位置上,其余各位为信息位 - P1 的海明位号为 2^(i-1)=2^0=1, 即 H1 为 P1。 - P2 的海明位号为 2^(i-1)=2^1=1, 即 H2 为 P2。 - P3 的海明位号为 2^(i-1)=2^2=4, 即 H4 为 P3。 (3) 分组以形成校验关系 - 每个数据位用多个校验位进行校验 - 满足条件:被校验数据位的海明位号等于校验该数据位的各校验位海明位号之和。 - 校验位不需要再被校验。 - Subtopic - Index(D) = Sum( Index (P) ) - D1 放在 H3 上, 由 P2 P1 校验: - 3 = 2^(2-1) + 2^(1-1) - D2 放在 H5 上, 由 P3 P1 校验: - 5 = 2^(3-1) + 2^(1-1) - D3 放在 H6 上, 由 P3 P2 校验: - 6 = 2^(3-1) + 2^(2-1) - D4 放在 H7 上, 由 P3 P2 P1 校验: - 7 = 2^(3-1) + 2^(2-1) + 2^(1-1) (4) 校验位取值 - 校验位 Pi 的值为第i组(由该校验位校验的数据位)所有位求异或。 - Subtopic - 1010 对应的海明码为1010010 (5) 海明码的校验原理 - 每个校验组分别利用校验位和参与形成该校验位的信息位进行奇偶校验检查,构成 k 个校验方程: - 若S3S2S1的值为“000”,则说明无错;否则说明出错,且这个数就是错误位的位号,如S3S2S1 = 001 说明第1位出错,即0出错,直接将该位取反就达到了纠错的目的。
“纠错”与“检错”

有定理 D + C = L - 1 (D >= C)

D 表示检错长度；
C 表示纠错长度；
L表示编码长度此定理来源于信息论，只需记住结论。

当有 C 位纠错时，至少有 C 位检错，此时 L = 2C+1
当有 D 位检错时，则纠错位长度可为 0 （只检错不纠错），此时 L = D + 1

3.4 流量控制与可靠传输机制

3.4.1 流量控制、可靠传输与滑动窗口机制

流量控制涉及对链路上的帧的发送速率的控制,以使接收方有足够的缓冲空间来接收每个帧。

停止-等待流量控制基本原理

发送方每发送一帧,都要等待接收方的应答信号,之后才能发送下一帧;

收方每接收一帧, 都要反馈一个应答信号,表示可接收下一帧,如果接收方不反馈应答信号,那么发送方必须一直等待。

每次只允许发送一帧,然后就陷入等待接收方确认信息的过程中,因而传输效率很低。

滑动窗口流量控制基本原理

概述

在任意时刻,发送方都维持一组连续的允许发送的帧的序号,称为发送窗口;同时接收方也维持一组连续的允许接收帧的序号,称为接收窗口。
发送窗口用来对发送方进行流量控制,而发送窗口的大小 WT 代表在还未收到对方确认信息的情况下发送方最多还可以发送多少个数据帧。
在接收端设置接收窗口是为了控制可以接收哪些数据帧和不可以接收哪些帧。
接收方, 只有收到的数据帧的序号落入接收窗口内时,才允许将该数据帧收下。若接收到的数据帧落在接收窗口之外,则一律将其丢弃。

发送和接收的处理

发送端每收到一个确认帧,发送窗口就向前滑动一个帧的位置,当发送窗口内没有可以发送的帧(即窗口内的帧全部是已发送但未收到确认的帧)时,发送方就会停止发送,直到收到接收方发送的确认帧使窗口移动,窗口内有可以发送的帧后,才开始继续发送。
接收端收到数据帧后,将窗口向前移一个位置,并发回确认帧,若收到的数据帧落在接收窗口之外,则一律丢弃。

重要特性:

只有接收窗口向前滑动(同时接收方发送了确认帧)时,发送窗口才有可能(只有发送方收到确认帧后才一定)向前滑动。

从滑动窗口的概念看,停止-等待协议、后退N帧协议和选择重传协议只在发送窗口大小与接收窗口大小上有所差别:

停止-等待协议:发送窗口大小=1,接收窗口大小=1。

后退N帧协议:发送窗口大小 > 1, 接收窗口大小=l

选择重传协议:发送窗口大小 > 1,接收窗口大小 > 1。

接收窗口的大小为1时,可保证帧的有序接收。

数据链路层的滑动窗口协议中,窗口的大小在传输过程中是固定的

可靠传输机制

使用确认和超时重传两种机制来完成。

确认

确认是一种无数据的控制帧;这种控制帧使得接收方可以让发送方知道哪些内容被正确接收。

超时重传

超时重传是指发送方在发送某个数据帧后就开启一个计时器,在一定时间内如果没有得到发送的数据帧的确认帧,那么就重新发送该数据帧, 直到发送成功为止。

自动重传请求.( Auto Repeat reQuest, ARQ) 通过接收方请求发送方重传出错的数据帧来恢复出错的帧,是通信中用于处理信道所带来差错的方法之一。

3.4.2单帧滑动窗口与停止、等待协议

停止-等待协议:发送窗口大小=1,接收窗口大小=1。
简单过程

发送方过程

连续出现相同序号的确认帧时,表明接收端收到了重复帧。帧序号以0和1交替；
发送帧后等待 ACK （此接收的ACK为期望发送的ACK序号）；
若 ACK 序号 = 1 - 发送序号，则删除上一个帧的副本，发送下一个，保留发送帧的副本，启动超时计时器；
若超时，则把副本重新发送一遍，重新计时。

接收方过程

接收帧，检查是否出错，
无错，则上交，发送下一个期望收到的 ACK
有错，则抛弃。

帧缓冲区

超时重发和判定重复帧的需要

3.4.3 多帧滑动窗口与后退N帧协议(GBN)

后退N帧协议:发送窗口大小 > 1, 接收窗口大小=l
若采用 n 比特对帧编号,则其发送窗口的尺寸 WT 应满足 1 <= WT <= 2^n - 1。
特点

发送方无须在收到上一个帧的ACK后才能开始发送下一帧,而是可以连续发送帧。
接收方只允许按顺序接收帧。

当接收方检测出失序的信息帧后,要求发送方重发最后一个正确接收的信息帧之后的所有未被确认的帧;
前一个帧在计时器超时后仍未返回其确认信息,则该帧被判为出错或丢失,此时发送方就重传该出错帧及随后的个帧。换句话说,接收方只允许按顺序接收帧。

优点

提高了信道的利用率

缺点

重传时，效率低。若信道的传输质量很差导致误码率较大时, 后退N帧协议不一定优于停止-等待协议。

过程

发送者

响应三个事件：

上层要发送数据调用时

如果发送窗口未满，则接收数据，分配一个帧序号给新产生的帧，发送帧，缓存此帧，同时设置超时时钟

如果发送窗口已满，则通知上层窗口已满。

收到了来自接收者的 ACKn

如果 n 大于发送窗口内的最小帧序号，则发送窗口向前移动至 n+1 ～ n+WT

否则，没有任何有效信息

超时时钟触发

重新发送超时的帧和其之后的所有帧，重置超时时钟。

发送方的 ACKn 表示前n个均正确接收

接收者

当接收者此时的窗口序号为 n 时

若接收到序号为 x == n 的帧，检测无误后，上交到上层，接收窗口向后移动一位，发送 ACKn+1；有误，丢弃。

若接收到序号为 x != n 的帧，丢弃。

3.4.4 多帧滑动窗口与选择重传协议(SR)

选择重传协议:发送窗口大小 > 1,接收窗口大小 > 1。
只重传出现差错的数据帧或计时器超时的数据帧,
必须加大接收窗口,以便先收下发送序号不连续1但仍处在接收窗口中的那些数据帧。

接收窗口 WR + 发送窗口 WT <= 2^n 接收窗口 WR 显然不应超过发送窗口 WT. WR <= WTWR <= 2^(n-1)。
接收窗口为最大值时, WTmax = WRmax = 2^(n-1)

所需缓冲区的数目等于窗口的大小,
过程

发送者

上层调用

如果发送窗口未满，则接收数据，分配一个帧序号给新产生的帧，发送帧，缓存此帧，同时设置超时时钟；

如果发送窗口已满，则通知上层窗口已满或缓存数据。

收到 ACKn

如果 n 处于发送窗口范围内，则标记 n 号帧为已接收。

若 n 为发送窗口最小序号，则窗口向前移至最小的未确认帧处，并发送帧（若已经发送则等待）。

如果 n 处于发送窗口外，则丢弃。

超时处理

每个已经发送的帧都有超时时钟。时钟触发，则重新发送对应的一个帧。

接收者

当接受到的帧序号为 x 时，且接受窗口为 [n,n + WR]
若帧序号为 x 的帧坏了，则发送 n 的 NAK。
若 x != n , 则：

发送 n 的 NAK；
判断 x 是否在接受窗口内，

若在接受窗口内且序号为 n 的帧未收到，则标记为已收到，且缓存此帧，而不交付上一层。
若不在接受窗口内，且 x < n, 则重新检查 x，并返回 ACKx。
若不在接受窗口内，且 x > n + WR, 则丢弃。

若 x == n , 则：

接受此帧，并且此序号以及之后已经缓存的连续序号的帧被交付到上一层，接收窗口向前移动到最小的未被交付的序号。

性能分析

T = 帧发送时间 + 重传时间 = 2 * 传播时延 + 确实帧发送时间 + 2 * 帧处理时间 + 帧发送时间

发送方从开始发送数据到收到第一个确认帧ACK为止，这段时间称为一个发送周期

信道利用率=发送时间/发送周期 = (发送比特/发送速率)/发送周期
信道吞吐率=信道利用率*发送方的发送速率

3.5 介质访问控制

主要任务

为使用介质的每个结点隔离来自同一信道上其他结点所传送的信号,以协调活动结点的传输。

来决定广播信道中信道分配的协议属于数据链路层的一个子层,称为介质访问控制(Medium Access Control, MAC)子层

局域网是一种广播式的网络（广域网是一种点对点的网络），所有联网计算机都共享一个公共信道，所以，需要一种方法能有效地分配传输介质的使用权，使得两对结点之间的通信不会发生相互干扰的情况，这种功能就叫介质访问控制。

常见的介质访问控制方法

信道划分介质访问控制
随机访问介质访问控制
轮询访问介质访问控制。其中前者是静态划分信道的方法,而后两者是动态分配信道的方法。

3.5.1 信道划分介质访问控制

将使用介质的每个设备与来自同一通信信道上的其他设备的通信隔离开来,把时域和频域资源合理地分配给网络上的设备。
多路复用技术

多个信号组合在一条物理信道上进行传输,使多个计算机或终端设备共享信道资源,提高了信道的利用率。
信道划分的实质就是通过分时、分频、分码等方法把原来的一条广播信道,逻辑上分为几条用于两个结点之间通信的互不干扰的子信道,实际上就是把广播信道转变为点对点信道。

信道划分介质访问控制

频分多路崖用(FDM)

将多路基带信号调制到不同频率载波上,再叠加形成一个复合信号的多路复用技术。

优点

分利用了传输介质的带宽,系统效率较高;
技术比较成熟, 实现也较容易。
缺点

为了防止子信道之间的干扰,相邻信道之间需要加入"保护频带”

时分多路复用(TDM)

将一条物理信道按时间分成若干时间片,轮流地分配给多个信号使用。

缺点

由于计算机数据的突发性,一个用户对已经分配到的子信道的利用率一般不高。

优化

统计时分多路复用(STDM)

是TDM的一种改进,它采用STDM帧,STDM帧并不固定分配时隙,而按需动态地分配时隙,当终端有数据要传送时,才会分配到时间片,因此可以提高线路的利用率。

波分多路复用(WDM)

波分多路复用即光的频分多路复用,它在一根光纤中传输多种不同波长(频率)的光信号,由于波长(频率)不同,各路光信号互不千扰,最后再用波长分解复用器将各路波长分解出来。

码分多路复用(CDM)

码分多路复用是采用不同的编码来区分各路原始信号的一种复用方式。

它既共享信道的频率,又共享时间。

码分多址(Code Division Multiple Access. CDMA)

每比特时间被分成农个更短的时间槽,称为码片(Chip)
每个站点被指定一个唯一的和位代码或码片序列。
发送1时,站点发送码片序列;发送0时,站点发送码片序列的反码。
为从信道中分离出各路信号,要求各个站点的码片序列相互正交。
例子

站点 A、B 同时发送给 C

若 A 站点的芯片序列为 (-1 -1 -1 +1 +1 -1 +1 +1)
且 B 站点的芯片序列为 (-1 -1 +1 -1 +1 +1 +1 -1)
验证正交：A ∙ B = sum(Ai * Bi) = 0
当 A 在链路中发送数据时，发送 1 (-1 -1 -1 +1 +1 -1 +1 +1) ，B 发送 0 (+1 +1 -1 +1 -1 -1 +1)；
则，在链路中的信号叠加为 (0 0 -2 2 0 -2 0 2);
当 C 收到这个叠加的序列后，想获得 A 的数据，则将收到的序列与A的序列点积，得 1。
当同理，想获得 B 的数据时，点积B的序列获得 -1 ，即0。

3.5.2 随机访问介质访问控制

不采用集中控制方式解决发送信息的次序问题,所有用户能根据自己的意愿随机地发送信息,占用信道全部速率。
为了解决随机接入发生的碰撞,每个用户需要按照一定的规则反复地重传它的帧,直到该帧无碰撞地通过。这些规则就是随机访问介质访问控制协议,

常用的协议有ALOHA协议、CSMA 协议、CSMA/CD协议和CSMA/CA协议等,
核心思想都是:胜利者通过争用获得信道, 从而获得信息的发送权。

随机介质访问控制实质上是一种将广播信道转化为点到点信道的行为

ALOHA 协议 (1) 纯ALOHA协议 - 基本思想 - 当网络中的任何一个站点需要发送数据时,可以不进行任何检测就发送数据。如果在一段时间内未收到确认,那么该站点就认为传输过程中发生了冲突。发送站点需要等待一段时间后再发送数据,直至发送成功。 - 吞吐量 - S=Ge^(-2G) - 当 G =0.5 时，S_MAX = 0.184 - 纯ALOHA网络的吞吐量很低 2) 时隙ALOHA协议 - 把所有各站在时间上同步起来,并将时间划分为一段段等长的时隙( Slot) , 规定只能在每个时隙开始时才能发送一个帧。 - 吞吐量 - S = Ge^(-G) - 当 G=1时, S_MAX =0.368

CSMA 协议

若每个站点在发送前都先侦听一下共用信道,发现信道空闲后再发送"则就会大大降低冲突的可能,从而提高信道的利用率 (1) 1-坚持 CSMA

过程

发送前首先侦听

空闲则以概率1 发送，即立即发送

忙，则持续侦听至空闲

冲突，则随机等待一段时间后重发。

特点

传播延迟对1-坚持CSMA协议的性能影响较大。 (2) 非坚持 CSMA

过程

发送前侦听

空闲则发送

忙，则放弃侦听，一个随机事件后重发。

特点

降低了多个结点等待信道空闲后同时发送数据导致冲突的概率,但也会增加数据在网络中的平均延迟。
信道利用率的提高是以增加数据在网络中的延迟时间为代价的。 (3) P-坚持 CSMA

过程

发送前侦听

忙则等待，并且持续侦听

空闲则以概率 p 发送，1-p 的概率推迟到下一个时隙。

特点

是非坚持CSMA协议和1-坚持CSMA协议的折中方案。

CSMA/CD 协议

适用于总线形网络或半双工网络环境。

载波帧听

“载波帧听〃就是发送前先侦听,即每个站在发送数据之前先要检测一下总线上是否有其他站点正在发送数据,若有则暂时不发送数据,等待信道变为空闲时再发送。

碰撞检测

“碰撞检测”就是边发送边侦听,即适配器边发送数据边检测信道上信号电压的变化情况,以便判断自己在发送数据时其他站点是否也在发送数据。

过程

侦听带信道空闲，则传输

忙，则等待到空闲在开始传输

传输过程中检测到冲突，则停止并发送 48 bit 的拥塞信号

由于冲突中止后，使用截断二进制指数算法来随机等待。

冲突恢复（等待）：

确定基本退避时间（一般是争用期时间 2τ）

K = min(重传次数, 10)

重传退避时间 = 2rτ，r 为随机从 [0, 2^k-1] 中选取，τ 为单程传播时延

重传 16 次后不成功则失败

最小帧长

为了确保发送站在发送数据的同时能检测到可能存在的冲突,需要在发送完帧之前就能收到自己发送出去的数据,即帧的传输时延至少要两倍于信号在总线中的传播时延
最小帧长 = 总线传播时延 * 数据传输率 * 2

CSMA/CA 协议

不能简单地搬用CSMA/CD协议,特别是碰撞检测部分。

接收信号的强度往往会远小于发送信号的强度,且在无线介质上信号强度的动态变化范围很大,因此若要实现碰撞检测,则硬件上的花费就会过大。

在无线通信中,并非所有的站点都能够听见对方,即存在“隐蔽站”问题。

实现碰撞避免的三种机制

预约信道

广播自己传输需要的时间长度

接收方收到数据帧或内容需回复一个 ack 帧
RTS/CTS

同 ACK 帧类似，用于解决“隐蔽站”问题

802.11 的 MAC 子层

操作模式

DCF: Distributed Coordination Function

使用 CSMA/CA
提供 RTS/CTS

主机向AP提出申请预约信道
信道广播CTS，非目标主机根据RTS的信息（计算占用时间）进入NAV

利用竞争窗口的二进制指数回退机制协调多个STA对共享链路的访问，避免出现因争抢介质而无法通信的情况

其核心思想是利用二进制指数回退机制减轻数据分组的碰撞以及实现发生碰撞后对分组的有限重传控制

过程：

第一个帧时，等待分布式帧间隔（DIFS）后发送该帧

之后的帧

等待 DIFS 后，

若空闲，则进入随机回退

若忙，则进入 Busy Medium

随机回退过程中，

首先从争用窗口选取一哥随机数（802.11中默认初试竞争窗口为 31）

每经过一个slot time，监听一次信道，空闲则随机回退计数减1

计数至 0 时，发送

AP 收到后在 SIFS 后发送 ACK 确认帧（此时又开始间隙）

未收到确认帧，争用窗口增大

回到 1.

几种帧间隔

SIFS：控制帧或下一个分片
PIFS：PCF帧
DIFS：DCF帧
EIFS：怀损帧重发等待

MAC 帧格式

Frame Control 各字段含义 2B

Protocol Version: 目前为0
Type: 帧类别, 有下面三种, 每个类别又有一些子类别
Subtype: 帧子类别, 与Type共同来决定一个帧的类型, 详细如下表所示
To DS/From DS: 指示帧目的地是否为DS(分布式系统), 可以简单地理解为是否【发往/来自】AP
More fragments: 指示是否还有分片(除去最后一个分片)
Retry: 指示当前帧是否为重传帧, 接收方收到后会删掉重复帧
Power management: 指示STA的电源管理模式, 1表示STA在数据交换完成后进入省电模式, 对于AP恒为0
More data: 指示AP为进入省电模式的STA进行帧缓存(来自DS)
WEP: 指示frame body是否使用WEP加密
Order: 指示将进行严格次序(StrictlyOrdered)传送

持续时间: 2B
地址1: 6B 一般链路的接收 MAC
地址2: 6B 一般链路的发送 MAC
地址3: 6B 路由器MAC
序号: 2B
地址4: 6B AP自组织模式中
信息主体: 0 - 2312B
CRC: 4B

PCF: Point Coordination Function

PCF作为DCF的补充，是一种可选的介质访问机制
提供了不必通过竞争即可使用介质的服务，为了满足实时业务需求
PCF以周期的形式进行帧的传输

每个周期包括一个无竞争阶段和一个竞争阶段

无竞争阶段(CFP: Contention-Free Period)
竞争阶段(CP: Contention Period)

3.5.3 轮询访问介质访问控制:令牌传递协议

通过一个集中控制的监控站,以循环方式轮询每个结点,再决定信道的分配。
一个令牌在各结点间以某个固定次序交换
令牌是由一组特殊的比特组合而成的帧。
当环上的一个站希望传送帧时,必须等待令牌。
一旦收到令牌,站点便可启动发送帧。帧中包括目的站的地址,以标识哪个站应接收此帧。
帧在环上传送时,不管该帧是否是发给本站点的,所有站点都进行转发,直到该帧回到它的始发站,并由该始发站撤销该帧。
帧的目的站除转发帔外,应针对该帧维持一个副本,并通过在帧的尾部设置“响应比特"来指示已收到此副本。
站点在发送完一帧后,应释放令牌,以便让其他站使用。
轮询介质访问控制非常适合负载很高的广播信道。

3.6 局域网

3.6.1 局域网的基本概念和体系结构

指在一个较小的地理范围(如一所学校)内,将各种计算机、外部设备和数据库系统等通过双绞线、同轴电缆等连接介质互相连接起来,组成资源和信息共享的计算机互联网络
主要特点

为一个单位所拥有,且地理范围和站点数目均有限。

所有站点共享较高的总带宽(即较高的数据传输率)。

较低的时延和较低的误码率。

各站为平等关系而非主从关系。

能进行广播和组播。

局域网的特性主要由三个要素决定

拓扑结构

1 星形结构;
2 环形结构;
3 总线形结构;
4 星形和总线形结合的复合型结构

传输介质

双绞线

双绞线为主流传输介质

铜缆
光纤等

介质访问控制方式

最重要的是介质访问控制方式,它决定着局域网的技术特性。

总线形局域网

令牌总线
CSMA/CD

环形局域网

令牌环

三种特殊的局域网拓扑实现

以太网

逻辑拓扑是总线形结构,物理拓扑是星形或拓展星形结构。

令牌环

逻辑拓扑是环形结构,物理拓扑是星形结构

FDDI

逻辑拓扑是环形结构,物理拓扑是双环结构。

3.6.2 以太网与 IEEE 802.3

描述物理层和数据链路层的MAC子层的实现方法。

是指符合DIX Ethernet V2标准的局域网,但DIX Ethernet V2标准与 IEEE 802.3标准只有很小的差别,因此通常将802.3局域网简称为以太网。

数据链路层拆分为两个子层:

逻辑链路控制(LLC)

与传输媒体无关,它向网络层提供无确认无连接、面向连接、带确认无连接、高速传送4种不同的连接服务类型。

媒体接入控制(MAC) 子层

与接入传输媒体有关的内容都放在MAC子层,它向上层屏蔽对物理层访问的各种差异,提供对物理层的统一访问接口,主要功能包括:组帧和拆卸帧、比特传输差错检测、透明传输。

以太网逻辑上采用总线形拓扑结构,以太网中的所有计算机共享同一条总线,信息以广播方式发送。

总线上使用的是广播通信

简化了通信流程并使用了 CSMA/CD方式对总线进行访问控制。
两项措施简化通信

用无连接的工作方式;
不对发送的数据帧编号,也不要求接收方发送确认,即以太网尽最大努力交付数据,提供的是不可靠服务,对于差错的纠正则由高层完成。

1.以太网的传输介质与网卡

传输介质

Subtopic

网卡：网络接口板[又称网络适配器(Adapter) 或网络接口卡(NetworkInterface Card， NIC) ]

工作在数据链路层的网路组件

控制着主机对介质的访问,因此网卡也工作在物理层,因为它只关注比特,而不关注任何地址信息和高层协议信息。

是局域网中连接计算机和传输介质的接口
功能

现与局域网传输介质之间的物理连接和电信号匹配
涉及帧的发送与接收、帧的封装与拆封、介质访问控制、数据的编码与解码及数据缓存功能等

出厂时都有一个唯一的代码,称为介质访问控制(MAC) 地址

用于控制主机在网络上的数据通信

2.以太网的MAC帧

每块网络适配器・ (网卡)都有一个地址,称为MAC地址,也称物理地址;

MAC地址长6 字节,一般用由连字符(或冒号)分隔的6个十六进制数表示,如02-60-8c-e4-b1-21高24位为厂商代码,低24位为厂商自行分配的网卡序列号。

网卡从网络上每收到一个MAC帧,首先要用硬件检查 MAC帧中的MAC地址。如果是发往本站的帧,那么就收下,否则丢弃。
以太网MAC帧格式

有两种标准：DIX Ethernet V2 和 IEEE 802.3
由于历史原因，现有 Ethernet V2 再有 IEEE 802.3，且前者比后者少 8 bit 长度。目前是 Ethernet V2 是主流。IEEE 802.3 的帧结构与 Ethernet V2 的不同点：
802.3 一共 14 bit，6 + 6 + 2，前12 bit 与V2一样，最后 2 bit 代表长度。
且由于 802.3 是在 802.2 以上构建的，所以 802.3 的 14 bit 后还紧跟着 802.2 的 8 bit。
网卡为了兼容两种协议,是这么来实现的:
网卡只发送 Ethernet2格式帧,可以接收两种格式的帧,怎么分辨两种格式呢?就是判断 length/ethertype 的那 2 bit 的内容，如果大于 1500 则为 Ethernet2,否则为802.3.

Subtopic

前导码

前导码:使接收端与发送端时钟同步。在帧前面插入的8字节可再分为两个字段:第一个字段共7字节,是前同步码,用来快速实现MAC帧的比特同步;第二个字段是帧开始定界符,表示后面的信息就是MAC帧。

地址

地址:通常使用6字节( 48bit) 地址(MAC地址)。

类型

类型:2字节,指出数据域中携带的数据应交给哪个协议实体处理。

数据

数据:46〜1500字节,包含高层的协议消息。由于CSMA/CD算法的限制,以太网帧必须满足最小长度要求64字节,数据较少时必须加以填充(0-46字节)。

46和1500是怎么来的?

首先,由CSMA/CD算法可知以太网帧的最短帧长为64B, 而MAC帧的首部和尾部的长度为18字节,所以数据最短为64-18 = 46字节。其次,最大的15GG 字节是规定的,没有为什么。

校验码(FCS)

校验码(FCS) : 4字节,校验范围从目的地址段到数据段的末尾,算法采用32位循环冗余码( CRC),不但需要检验MAC帧的数据部分,还要检验目的地址、源地址和类型字段,但不校验前导码。

3.高速以太网 (1) 100BASE-T 以太网 - 既支持全双工方式,又支持半双工方式。 - 全双工方式下，无冲突发生，不使用CSMA/CD协议；半双工方式下，使用 CSMA/CD - 使用 100BASE-T 传输介质 - 最长电缆长度为 100m，帧间隔从 9.6 微秒改为 0.96 微秒。 (2) 吉比特以太网 - 在 1Gb/s下用全双工和半双工两种方式工作。 - 使用 802.3 协议规定的帧格式。 - 在半双工方式下使用CSMA/CD协议(全双工方式不需要使用CSMA/CD协议)。 (3) 10吉比特以太网 - 只使用光纤作为传输媒体。 - 只工作在全双工方式 - 不使用 CSMA/CD 协议

3.6.3 IEEE 802.11

IEEE 802.11是无线局域网的一系列协议标准,包括802.11a和802.11b等。它们制定了 MAC 层协议,运行在多个物理层标准上。
除基本的协调访问问题外,标准还进行错误控制(以克服通道固有的不可靠性)、适宜的寻址和关联规程(以处理站的可携带性和移动性)、互联过程(以扩展无线站的通信范围),并且允许用户在移动的同时进行通信。
802.11的MAC层采用CSMA/CA协议进行介质访问控制。

有固定基础设施无线局域网

802.11标准规定无线局域网的最小构件是基本服务集(Basic Service Set, BSS)。

一个基本服务集包括一个基站和若干移动站。

基本服务集中的基站也称接入点(Access Point, AP),其作用和网桥相似。

所有的站在本BSS内都可以直接通信,但在与本BSS外的站通信时都要通过本BSS的基站。
一个基本服务集可以是孤立的,也可通过接入点(AP)连接到一个主干分配系统(Distribution System, DS),然后再接入另一个基本服务集,构成扩展的服务集(Extended Service Set, ESS),扩展服务集(ESS)还可通过称为门桥(Portal)的设备为无线用户提供到非802.11无线局域网(如到有线连接的因特网)的接入。门桥的作用相当于一个网桥。

2.无固定基础设施无线局域网自组织网络

由一些平等状态移动站相互通信组成的临时网络。各结点之间地位平等,中间结点都为转发结点,这些结点都具有路由器功能。
一些可移动设备发现在它们附近还有其他可移动设备,并且要求和其他移动设备通信。
移动自组织网络是把移动性扩展到无线领域中的自治系统,具有自己特定的路由选择协议,并且可以不和因特网相连,

3.6.4 令牌环网的基本原理

令牌环网的基本原理如图3.27所示。令牌环网的每一站通过电缆与环接口干线耦合器(TCU) 相连。

TCU的主要作用是,传递所有经过的帧,为接入站发送和接收数据提供接口。
TCU的状态也有两个

发送状态
收听状态

媒体接入控制机制

采用的是分布式控制模式的循环方法
令牌实际上是一个特殊格式的MAC控制帧,它本身并不包含信息,仅控制信道的使用,确保在同一时刻只有一个结点能够独占信道。
站点只有取得令牌后才能发送数据帧,因此令牌环网不会发生碰撞。
在物理上采用星形拓扑结构,但逻辑上仍是环形拓扑结构,
传递过程

网络空闲时,环路中只有令牌帧在循环传递。

令牌传递到有数据要发送的站点处时,该站点就修改令牌中的一个标志位,并在令牌中附加自己需要传输的数据,将令牌变成一个数据帧,然后将这个数据帧发送出去。

数据帧沿着环路传输,接收到的站点一边转发数据,一边查看帧的目的地址。如果目的地址和自己的地址相同,那么接收站就复制该数据帧以便进一步处理。

数据帧沿着环路传输,直到到达该帧的源站点,源站点接收到自己发出去的数据帧后便不再进行转发。同时,发送方可以通过检验返回的数据帧来查看数据传输过程中是否有错,若有错则重传该帧。

源站点传送完数据后,重新产生一个令牌,并将令牌传递给下一个站点,以交出对媒体的访问权限。

3.7 广城网

3.7.1 广域网的基本概念

通常是覆盖范围很广的长距离网络
结点交换机的链路都是高速链路, 它可以长达几千千米的光缆线路,也可以是长达几万千米的点对点卫星链路。
广域网首要考虑的问题是通信容量必须足够大,以便支持日益增长的通信量。
由一些结点交换机及连接这些交换机的链路组成。
结点交换机的功能是将分组存储并转发。
结点之间都是点到点连接
广域网和局域网的区别与联系
一个重要问题是路由选择和分组转发。

路由选择协议负责搜索分组从某个结点到目的结点的最佳传输路由，以便构造路由表。然后从路中表再构造中转发分组的转发表c分组是通过转发表进行转发的。

PPP协议和HDLC协议是目前最常用的两种广域网数据链路层控制协议。

3.7.2 PPP 协议

串行线路通信的面向字节的协议

所有PPP帧的长度都是整数个字节

三个组成部分

链路控制协议(LCP)

链路控制协议(LCP)。一种扩展链路控制协议,用于建立、配置、测试和管理数据链路。

网络控制协议(NCP) 2) 网络控制协议(NCP)。PPP协议允许同时采用多种网络层协议,每个不同的网络层协议要用一个相应的NCP来配置,为网络层协议建立和配置逻辑连接。
—个将IP数据报封装到串行链路的方法 3) —个将IP数据报封装到串行链路的方法。IP数据报在PPP帧中就是其信息部分,这个信息部分的长度受最大传送单元(MTU)的限制。

PPP帧的格式

标志字段

标志字段(Flag)仍为 0x7E (01111110)

地址字段

地址字段(Address)占1字节,规定为 OxFF,固定不变的

控制字段

控制字段(Control)占1字节,规定为 0x03固定不变的

协议段

协议段,占2字节说明信息段中运载的是什么种类的分组。

以比特0开始的是诸如IP、IPX和AppleTalk这样的网络层协议;以比特1开始的被用来协商其他协议,包括LCP及每个支持的网络层协议的一个不同的NCPo

信息段

信息段。长度是可变的,大于等于0且小于等于1500B
为了实现透明传输,当信息段中出现和标志字段一样的比特组合时,必须采用一些措施来改进。
因为PPP是点对点的,并不是总线形,所以无须采用CSMA/CD协议,自然就没有最短帧,所以信息段占0〜1500字节,而不是46〜1500字节。
帧检验序列(FCS),占2字节,即循环冗余码检验中的冗余码。
检验区包括地址字段、控制字段、协议字段、信息字段。

状态图

Subtopic

特点

PPP提供差错检测但不提供纠错功能,只保证无差错接收(通过硬件进行CRC校验)。

它是不可靠的传输协议,因此也不使用序号和确认机制。

它仅支持点对点的链路通信,不支持多点线路。

PPP只支持全双工链路。

PPP的两端可以运行不同的网络层协议,但仍然可使用同一个PPP进行通信。

PPP是面向字节的,当信息字段出现和标志字段一致的比特组合时,PPP有两种不同的处理方法:若PPP用在异步线路(默认),则采用字节填充法;若PPP用在SONET/SDH 等同步线路,则协议规定采用硬件来完成比特填充(和HDLC的做法一样)。

3.7.3 HDLC 协议

面向比特的数据链路层协议。

协议不依赖于任何一种字符编码集;
数据报文可透明传输,用于实现透明传输的“0比特插入法”易于硬件实现;

特点

全双工通信,有较高的数据链路传输效率;
所有帧采用CRC检验,对信息帧进行顺序编号,可防止漏收或重发,传输可靠性高;
传输控制功能与处理功能分离,具有较大的灵活性。

基本配置

非平衡配置

非平衡配置的特点是由一个主站控制整个链路的工作。

平衡配置 2) 平衡配置的特点是链路两端的两个站都是复合站,每个复合站都可以平等地发起数据传输,而不需要得到对方复合站的允许。

主站

主站负责控制链路的操作,主站发出的帧称为命令帧。

从站

从站受控于主站,按主站的命令进行操作;发出的帧称为响应帧。

复合站

既具有主站的功能,又具有从站的功能,所以这类站称为复合站"它可以发出命令帧和响应帧。

数据操作方式

正常响应方式。这是一种非平衡结构操作方式,即主站向从站传输数据,从站响应传输, 但从站只有在收到主站的许可后,才可进行响应。
异步平衡方式。这是一种平衡结构操作方式。在这种方式中,每个复合站都可以进行对另一站的数据传输。
异步响应方式。这是一种非平衡结构操作方式。在这种方式中,从站即使未受到主站的允许,也可进行传输。

HDLC 帧

标志字段 F,为01111110。

在接收端只要找到标志字段就可确定一个帧的位置。
HDLC协议采用比特填充的首尾标志法实现透明传输。
在发送端,当一串比特流数据中有5个连续的1时, 就立即在其后填入一个0。
接收帧时,先找到F字段以确定帧的边界,接着对比特流进行扫描。每当发现5个连续的1时,就将其后的一个0删除,以还原成原来的比特流。

地址字段 A, 共8位,

在使用非平衡方式传送数据时,站地址字段总是写入从站的地址;在使用平衡方式传送数据时,站地址字段填入的是应答站的地址。

控制字段 c，共8位

信息帧

信息帧(I),第1位为0,用来传输数据信息,或使用捎带技术对数据进行确认。

监督帧 2) 监督帧(S),第1、2位分别为1、0,用于流量控制和差错控制,执行对信息帧的确认、请求重发和请求暂停发送等功能;
无编号帧 3) 无编号帧(U),第1、2位均为L用于提供对链路的建立、拆除等多种控制功能。

3.8 数据链路层设备

3.8.1 网桥的概念及其基本原理

两个或多个以太网通过网桥连接后,就成为一个覆盖范围更大的以太网,而原来的每个以太网就称为一个网段
网桥工作在链路层的MAC子层,可以使以太网各网段成为隔离开的碰撞域
网桥必须具有路径选择的功能,接收到帧后,要决定正确的路径,将该帧转送到相应的目的局域网站点。
网桥的基本特点:

1网桥必须具备寻址和路径选择能力,以确定帧的传输方向;
2从源网络接收帧,以目的网络的介质访问控制协议向目的网络转发该帧;
3网桥在不同或相同类型的LAN 之间存储并转发帧,必要时还进行链路层上的协议转换。

注意,一般情况下,存储转发类设备都能进行协议转换,即连接的两个网段可以使用不同的协议;

4网桥对接收到的帧不做任何修改, 或只对帧的封装格式做很少的修改;
5网桥可以通过执行帧翻译互联不同类型的局域网,即把原协议的信息段的内容作为另一种协议的信息部分封装在帧中;
6网桥应有足够大的缓冲空间,因为在短时间内帧的到达速率可能高于转发速率。

网桥的优点:

1能过滤通信量;
2扩大了物理范围;
3可使用不同的物理层;
4可互联不同类型的局域网;
5提高了可靠性;
6性能得到改善。

网桥的缺点

增大了时时延

MAC 子层没有流量控制功能

控制需要用到编号机制，编号机制的实现在 LLC 子层

3不同MAC子层的网段桥接在一起时,需要进行帧格式的转换;
4网桥只适合于用户数不多和通信量不大的局域网,否则有时还会因传播过多的广播信息而产生网络拥塞,这就是所谓的广播风暴。

网桥类别（路由算法不同）

透明网桥(选择的不是最佳路由)

以混杂方式工作

到达帧的路由选择过程取决于源LAN和目的LAN:

1如果源LAN和目的LAN相同,那么丢弃该帧;
2如果源LAN 和目的LAN不同,那么转发该帧;
3如果目的LAN未知,那么扩散该帧。

转发表

基本思想

若从站A发出的帧从某端口进入网桥,那么从这个端口出发沿相反方向一定可把一个帧传送到站A。

过程

接收

每收到一个帧,就记下其源地址和进入网桥的端口,作为转发表中的一个项目(源地址、进入的接口和时间)。
在建立转发表时,把帧首部中的源地址写在“地址” 一栏的下面。

发送

在转发帧时,则根据收到的帧首部中的目的地址来转发。
时就把在“地址〃栏下面已经记下的源地址当作目的地址,而把记下的进入端口当作转发端口。

避免转发的帧在网络中不断地“兜圈子七

使用了一种生成树算法(无环),以确保每个源到每个目的地只有唯一的路径。

使得整个扩展局域网在逻辑上形成树形结构, 所以工作时逻辑上没有环路,但生成树一般不是最佳路由。

源路由网桥(选择的是最佳路由)

作用

路由选择由发送数据帧的源站负责
网桥只根据数据真正的路由信息对帧进行接收和转发。

特点

源路由网桥对主机是不透明的,主机必须知道网桥的标识及连接到哪个网段上。

路由选择

由发送帧的源站负责
过程

在未知路径前,源站要先发送一个发现帧;

帮助源站确定整个网络可以通过的帧的最大长度

途中的每个网桥都转发此帧,最终该发现帧可能从多个途径到达目的站;
目的站也将一一发送应答帧;
每个应答帧将通过原路径返回,途经的网桥把自己的标志记录在应答帧中;
源站选择出一个最佳路由。
以后,凡从这个源站向该目的站发送的帧的首部,都必须携带这一路由信息。

比较

若在两个以太网之间使用并联的源路由网桥,则还可使通信量较平均地分配给每个网桥。
采用透明网桥时,只能使用生成树,而使用生成树一般并不能保证所用的路由是最佳的,也不能在不同的链路中进行负载均衡。
帧爆炸问题

透明网桥：数量为线性函数
源路由网桥：数量为指数型增加

3.8.2 局域网交换机及其工作原理

局域网交换机

从本质上说,以太网交换机是一个多端口的网桥,它工作在数据链路层

交换机能经济地将网络分成小的冲突域,为每个工作站提供更高的带宽

利用以太网交换机还可以方便地实现虚拟局域网(VirtualLAN, VLAN) , VLAN不仅可以隔离冲突域,而且可以隔离广播域。

2、原理

检测从以太端口来的数据帧的源和目的地的MAC (介质访问层) 地址,
然后与系统内部的动态查找表进行比较,若数据帧的MAC地址不在查找表中,则将该地址加入查找表,并将数据帧发送给相应的目的端口。

特点

以太网交换机的每个端口都直接与单台主机相连(普通网桥的端口往往连接到以太网的一个网段),并且一般都工作在全双工方式。
以太网交换机能同时连通许多对端口,使每对相互通信的主机都能像独占通信媒体那样, 无碰撞地传输数据。
以太网交换机也是一种即插即用设备(和透明网桥一样),其内部的帧的转发表也是通过自学习算法自动地逐渐建立起来的。
以太网交换机由于使用了专用的交换结构芯片,因此交换速率较高。
以太网交换机独占传输媒体的带宽。

4。两种交换模式

直通式交换机

只检杳帧的目的地址

帧在接收后几乎能马上被传出去

速度快,但缺乏智能性和安全性,也无法支持具有不同速率的端口的交换。

存储转发式交换机

先将接收到的帧缓存到高速缓存器中,并检查数据是否正确,确认无误后通过查找表转换成输出端口将该帧发送出去。

如果发现帧有错,那么就将其丢弃。

存储转发式的优点是可靠性高,并能支持不同速率端口间的转换,缺点是延迟较大。