3.1数据链路层的功能
    数据链路层在物理层提供服务的基础上向网络层提供服务，其最基本的服务是将源自网络层来的数据可靠地传输到相邻节点的目标机网络层。其主要作
    用是加强物理层传输原始比特流的功能，将物理层提供的可能出错的物理连接改造成为逻辑上无差错的数据链路，使之对网络层表现为一条无差错的链路。
    功能一、为网络层提供服务
    1. 无确认的无连接服务。源机器发送数据帧时不需先建立链路连接，目的机器收到数据帧时不需发回确认。对丢失的帧，数据链路层不负责重发而交给上
    层处理。适用于实时通信或误码率较低的通信信道，如以太网。
    2. 有确认的无连接服务。源机器发送数据帧时不需先建立链路连接，但目的机器收到数据帧时必须发回确认。源机器在所规定的时间内未收到确定信号
    时，就重传丢失的帧，以提高传输的可靠性。该服务适用于误码率较高的通信信道，如无线通信。
    3. 有确认的面向连接服务。帧传输过程分为三个阶段：建立数据链路、传输帧、释放数据链路。目的机器对收到的每一帧都要给出确认，源机器收到确认
    后才能发送下一帧，因而该服务的可靠性最高。该服务适用于通信要求（可靠性、实时性）较高的场合。
    注：有连接就一定要有确认，即不存在无确认的面向连接的服务。
    功能二、链路管理：数据链路层连接的建立、维持和释放过程称为链路管理，它主要用于面向连接的服务。
    功能三、组帧：帧定界、帧同步与透明传输。
    功能四、流量控制。
    功能五、差错控制（帧错/位错）。
    3.2组帧
    封装成帧：在一段数据的前后部分添加首部和尾部，这样就构成了一个帧。接收端在收到物理层上交的比特流后，就能根据首部和尾部的标记，从收到的比
    特流中识别帧的开始和结束。组帧主要解决帧定界、帧同步、透明传输等问题。
    •帧定界：首部和尾部包含许多的控制信息，他们的一个重要作用是确定帧的界限。
    •帧同步：接收方应当能从接收到的二进制比特流中区分出帧的起始和终止。
    •透明传输：不管所传数据是什么样的比特组合，都应当能够在链路上传送。当数据中恰好出现与帧定界符相同的比特组合（会误认为“传输结束”而丢
    弃后面的数据，那么就要采取有效的措施解决这个问题，即透明传输。因此，链路层“看不见”有什么妨碍数据传输的东西。
    组帧的四种方法：
    1.字符计数法
    在帧头部使用一个计数字段来标明帧内字符数（计数字段提供的字节数包含自身所占用的一个字节）。
    这种方法最大的问题在于如果计数字段出错，即失去了帧边界划分的依据，那么接收方就无法判断所传输帧的结束位和下一帧的开始位，收发双方将失
    去同步，从而造成灾难性后果。
    2.字符填充法
    使用特定字符来定界一帧的开始与结束。
    3.零比特填充法
    零比特填充法允许数据帧包含任意个数的比特，也允许每个字符的编码包含任意个数的比特。用0111110来标志一帧的开始和结束。
    发送方：在信息位中遇到5个连续的“1”时，将自动在其后插入一个“0” ；
    接收方：每收到5个连续的“1”时，自动删除后面紧跟的“0”，以恢复原信息。
    零比特填充法很容易由硬件来实现，性能优于字符填充法。
    4.违规编码法
    在物理层进行比特编码时，通常采用违规编码法。例如，曼彻斯特编码方法将数据比特“1 ”编码成“高-低”电平对，将数据比特“0”编码成“低-
    高”电平对，而“高-高”电平对和“低-低”电平对在数据比特中是违规的（即没有采用）。可以借用这些违规编码序列来定界帧的起始和终止。
    违规编码法不需要采用任何填充技术，便能实现数据传输的透明性，但它只适用于采用冗余编码的特殊编码环境。
    置D由于字节计数法中计数字段的脆弱性和字符填充法实现上的复杂性与不兼容性，目前较常用的组帧方法是比特填充法和违规编码法。
    33差错控制
    实际通信链路都不是理想的，比特在传输过程中可能会产生差错，1可能会变成0, 0也可能会变成1,这就是比特差错。比特差错是传输差错中的
    种，本节仅讨论比特差错。
    通常利用编码技术进行差错控制，主要有两类：自动重传请求ARQ和前向纠错FEC。在ARQ方式中，接收端检测出差错时，就设法通知发送端重发，直
    到接收到正确的码字为止。在FEC方式中，接收端不但能发现差错，而且能确定比特串的错误位置，从而加以纠正。因此，差错控制又可分为检错编码和纠
    错编码。
    _、检错编码
    检错编码都采用冗余编码技术，其核心思想是在有效数据（信息位）被发送前，先按某种关系附加一定的冗余位，构成一个符合某一规则的码字后再发
    送。当要发送的有效数据变化时，相应的冗余位也随之变化，使得码字遵从不变的规则。接收端根据收到的码字是否仍符合原规则来判断是否出错。
    1. 奇偶校验码
    奇偶校验码是奇校验码和偶校验码的统称，是一种最基本的检错码。它由n-1位信息元和1位校验元组成，如果是奇校验码，那么在附加一个校验元后，
    码长为n的码字中“1”的个数为奇数；如果是偶校验码，那么在附加一个校验元以后，码长为n的码字中“1”的个数为偶数。它只能检测奇数位的出错情
    况，但并不知道哪些位错了，也不能发现偶数位的出错情况。
    2. 循环冗余码（过程略）
    循环冗余码（CRC）又称多项式码。通过循环冗余码（CRC）的检错技术，数据链路层做到了对帧的无差错接收。也就是说，凡是接收端数据链路层接
    收的帧，我们都认为这些帧在传输过程中没有产生差错；而接收端丢弃的帧虽然也收到了，但最终因为有差错而被丢弃，即未被接受。
    U循环冗余码（CRC）是具有纠错功能的，只是数据链路层仅使用了它的检错功能，检测到帧出错则直接丢弃，因此本节将CRC放在检错编码中介
    绍。
    二、纠错编码
    最常见的纠错编码是海明码，其实现原理是在有效信息位中加入几个校验位形成海明码，并把海明码的每个二进制位分配到几个奇偶校验组中。当某一
    位出错后，就会引起有关的几个校验位的值发生变化，这不但可以发现错位，而且能指出错位的位置，为自动纠错提供依据。现以数据码1010为例讲述海
    明码的编码原理和过程。
    1. 确定海明码的位数
    2. 确定校验位的分布
    3. 分组以形成校验关系
    4. 校验位取值校验位P
    5. 海明码的校验原理
    3.4流量控制与可靠传输机制
    一、流量控制、可靠传输与滑动窗口机制
    流量控制涉及对链路上的帧的发送速率的控制，以使接收方有足够的缓冲空间来接收每个帧。例如，在面向帧的自动重传请求系统中，当待确认帧的数
    量増加时，有可能超出缓冲存储空间而造成过载。流量控制的基本方法是由接收方控制发送方发送数据的速率，常见的方式有两种：停止-等待协议和滑动
    窗口协议。
    1. 停止-等待流量控制基本原理
    发送方每发送一帧，都要等待接收方的应答信号，之后才能发送下一帧；接收方每接收一帧，都要反馈一个应答信号，表示可接收下一帧，如果接收方
    不反馈应答信号，那么发送方必须一直等待。每次只允许发送一帧，然后就陷入等待接收方确认信息的过程中，因而传输效率很低。
    2. 滑动窗口流量控制基本原理
    在任意时刻，发送方都维持一组连续的允许发送的帧的序号，称为发送窗口 ；同时接收方也维持一组连续的允许接收帧的序号，称为接收窗口。发送窗
    口用来对发送方进行流量控制，而发送窗口的大小W代表在还未收到对方确认信息的情况下发送方最多还可以发送多少个数据帧。同理，在接收端设置接收
    窗口是为了控制可以接收哪些数据帧和不可以接收哪些帧。在接收方，只有收到的数据帧的序号落入接收窗口内时，才允许将该数据帧收下。若接收到的数
    据帧落在接收窗口之外，则一律将其丢弃。
    发送端每收到一个确认帧，发送窗口就向前滑动一^帧的位置，当发送窗口内没有可以发送的帧（即窗口内的帧全部是已发送但未收到确认的帧）时，
    发送方就会停止发送，直到收到接收方发送的确认帧使窗口移动，窗口内有可以发送的帧后，才开始继续发送。接收端收到数据帧后，将窗口向前移一个位置，并发回确认帧，若收到的数据帧落在接收窗口之外，则一律丢弃。 滑动窗口有以下重要特性：
    （1） 只有接收窗口向前滑动（同时接收方发送了确认帧）时，发送窗口才有可能（只有发送方收到确认帧后才一定）向前滑动。
    （2） 从滑动窗口的概念看，停止-等待协议、后退N帧协议和选择重传协议只在发送窗口大小与接收窗口大小上有所差別：
    •停止-等待协议：发送窗口大小=1,接收窗口大小=1。
    •后退N帧协议：发送窗口大小＞1,接收窗口大小=1。
    •选择重传协议：发送窗口大小＞1,接收窗口大小＞1。
    （3） 接收窗口的大小为1时，可保证帧的有序接收。
    （4） 数据链路层的滑动窗口协议中，窗口的大小在传输过程中是固定的（注意与第5章传输层的滑动窗口协议的区别）。
    3.可靠传输机制
    数据链路层的可靠传输通常使用确认和超时重传两种机制来完成。确认是一种无数据的控制帧，这种控制帧使得接收方可以让发送方知道哪些内容被正
    确接收。有些情况下为了提高传输效率，将确认捎带在一个回复帧中，称为捎带确认。超时重传是指发送方在发送某个数据帧后就开启一个计时器，在一定
    时间内如果没有得到发送的数据帧的确认帧，那么就重新发送该数据帧，直到发送成功为止。
    自动重传请求（Auto Repeat reQuest, ARQ）通过接收方请求发送方重传出错的数据帧来恢复出错的帧，是通信中用于处理信道所带来差错的方法之
    —。传统自动重传请求分为三种，即停止-等待（Stop-and-Wait） ARQ、后退N帧（Go-Back-N） ARQ和选择性重传（Selective Repeat） ARQ。后两种协议
    是滑动窗口技术与请求重发技术的结合，由于窗口尺寸开到足够大时，帧在线路上可以连续地流动，因此又称其为连续ARCH办议。
    注意，在数据链路层中流量控制机制和可靠传输机制是交织在一起的。注意：现有的实际有线网络的数据链路层很少采用可靠传输（不同于0SI参考模
    型的思路），因此大多数教材把这部分内容放在第5章运输层中讨论，本书按照408考纲，不做变动。
    二、单帧滑动窗口与停止-等待协议
    在停止-等待协议中，源站发送单个帧后必须等待确认，在目的站的回答到达源站之前，源站不能发送其他的数据帧。从滑动窗口机制的角度看，停止-
    等待协议相当于发送窗口和接收窗口大小均为1的滑动窗口协议。
    在停止-等待协议中，除数据帧丢失夕卜，还可能出现以下两种差错。
    到达目的站的帧可能已遭破坏，接收站利用前面讨论过的差错检测技术检出后，简单地将该帧丢弃。为了对付这种可能发生的情况，源站装备了计时
    器。在一个帧发送之后，源站等待确认，如果在计时器计满时仍未收到确认，那么再次发送相同的帧。如此重复，直到该数据帧无错误地到达为止。
    另一种可能的差错是数据帧正确而确认帧被破坏，此时接收方已收到正确的数据帧，但发送方收不到确认帧，因此发送方会重传已被接收的数据帧，接
    收方收到同样的数据帧时会丢弃该帧，并重传一个该帧对应的确认帧。发送的帧交替地用0和1来标识,肯定确认分别用ACK0和ACK1来表示，收到的确认有
    误时，重传已发送的帧。对于停止-等待协议，由于每发送一个数据帧就停止并等待,因此用1 bit来编号就已足够。在停止-等待协议中，若连续出现相同发送
    序号的数据帧，表明发送端进行了超时重传。连续出现相同序号的确认帧时，表明接收端收到了重复帧。
    此外，为了超时重发和判定重复帧的需要，发送方和接收方都须设置一个帧缓冲区。发送端在发送完数据帧时，必须在其发送缓存中保留此数据帧的副
    本，这样才能在出差错时进行重传。只有在收到对方发来的确认帧ACK时，方可清除此副本。
    由图3.9可知，停止-等待协议通信信道的利用率很低。为了克服这一缺点，就产生了另外两种协议，即后退N帧协议和选择重传协议。
    三、多帧滑动窗口与后退N帧协议（GBN）
    在后退N帧式ARQ中，发送方无须在收到上一个帧的ACK后才能开始发送下一帧，而是可以连续发送帧。当接收方检测出失序的信息帧后，要求发送方
    重发最后一个正确接收的信息帧之后的所有未被确认的帧；或者当发送方发送了 N个帧后，若发现该N个帧的前一个帧在计时器超时后仍未返回其确认信
    息，则该帧被判为出错或丢失，此时发送方就不得不重传该出错帧及随后的N个帧。换句话说，接收方只允许按顺序接收帧。
    如图3.10所示，源站向目的站发送数据帧。当源站发完◦号帧后，可以继续发送后续的1号帧、2号帧等。源站每发送完一帧就要为该帧设置超时计时
    器。由于连续发送了许多帧，所以确认帧必须要指明是对明卜帧进行确认。为了减少开销，GBN协议还规定接收端不一定每收到一个正确的数据帧就必须立
    即发回一个确认帧，而可以在连续收到好几个正确的数据帧后，才对最后一个数据帧发确认信息，或者可在自己有数据要发送时才将对以前正确收到的帧力口
    以捎带确认。这就是说，对某一数据帧的确认就表明该数据帧和此前所有的数据帧均已正确无误地收到。在图3.10中，ACKn表示对第n号帧的确认，表示接
    收方已正确收到第n号帧及以前的所有帧，下一次期望收到第n + 1号帧（也可能是第◦号帧）。接收端只按序接收数据帧。虽然在有差错的2号帧之后接着又
    收到了正确的6个数据帧，但接收端都必须将这些帧丢弃。接收端虽然丢弃了这些不按序的无差错帧，但应重复发送已发送的最后一个确认帧ACK1 （这是为
    了防止已发送的确认帧ACK1丢失）。
    后退N帧协议的接收窗口为1,可以保证按序接收数据帧。若采用n比特对帧编号，则其发送窗口的尺寸W应满足1SW完^2”-1。若发送窗口的尺寸大于
    2”-1,则会造成接收方无法分辨新帧和旧帧（请参考本章疑难点3）。
    从图3.10不难看出，后退N帧协议一方面因连续发送数据帧而提高了信道的利用率，另一方面在重传时又必须把原来已传送正确的数据帧进行重传（仅
    因这些数据帧的前面有一个数据帧出了错），这种做法又使传送效率降低。由此可见，若信道的传输质量很差导致误码率较大时，后退N帧协议不一定优于
    停止-等待协议。
    四、多帧滑动窗口与选择重传协议（SR）
    为进一步提高信道的利用率，可设法只重传出现差错的数据帧或计时器超时的数据帧，但此时必须加大接收窗口，以便先收下发送序号不连续但仍处在
    接收窗口中的那些数据帧。等到所缺序号的数据帧收到后再一并送交主机。这就是选择重传ARQ协议。
    在选择重传协议中，每个发送缓冲区对应-一个计时器，当计时器超时时，缓冲区的帧就会重传。另外，该协议使用了比上述其他协议更有效的差错处
    理策略，即一旦接收方怀疑帧出错，就会发一个否定帧NAK给发送方，要求发送方对NAK中指定的帧进行重传，如图3.11所示。
    选择重传协议的接收窗口尺寸W和发送窗口尺寸W都大于1,一次可以发送或接收多个帧。若采用n比特对帧编号，为了保证接收方向前移动窗口后，新
    窗口序号与旧窗口序号没有重叠部分，需要满足条件：接收窗口WR +发送窗口WS2”。假定仍然采用累计确认的方法，并且接收窗口WR显然不应超过发送
    窗口Wq （否则无意义），那么接收窗口尺寸不应超过序号范围的一半，&PWR<201）。接收窗口为最大值时，WTmax = WRmax = 2 （1）。需要提醒读者
    选择重传协议可以避免重复传送那些本已正确到达接收端的数据帧，但在接收端要设置具有相当容量的缓冲区来暂存那些未按序正确收到的帧。接收端
    不能接收窗口下界以下或窗口上界以上的序号的帧，因此所需缓冲区的数目等于窗口的大小，而不是序号数目。
    在往年统考真题中曾经出现过对“信道效率” “信道的吞吐率”等概念的考查，有些读者未接触过“通信原理”等相关的课程，可能对这些概念不太熟
    悉，在这里给读者补充一下。
    信道的效率，也称信道利用率。可从不同的角度来定义信道的效率，这里给出一种从时间角度的定义：信道效率是对发送方而言的，是指发送方在一个
    发送周期的时间内，有效地发送数据所需要的时间占整个发送周期的比率。
    例如，发送方从开始发送数据到收到第一个确认帧为止，称为一个发送周期，设为T,发送方在这个周期内共发送L比特的数据，发送方的数据传输速率
    为C,则发送方用于发送有效数据的时间为LIC,在这种情况下，信道的利用率为（L/C） /T。
    从上面的讨论可以发现，求信道的利用率主要是求周期时间T和有效数据发送时间LC,在题目中，这两个量一般不会直接给出，需要读者根据题意自行
    计算。
    信道吞吐率=信道利用率x发送方的发送速率。
    本节习题有不少是关于信道利用率和信道吞吐率的，以帮助读者理解和记忆这两个概念。流量控制的三种滑动窗口协议的信道利用率是一个关键知识
    点，希望读者能结合习题，自行推导。
    3.5介质访问控制
    主要任务：为使用介质的每个结点隔离来自同一｛言道上其他结点所传送的信号，以协调活动结点的传输。
    介质访问控制（MAC）子层：决定广播信道中信道分配的协议属于数据链路层的一个子层。
    介质访问控制的内容：采取一定的措施，使得两对结点之间的通信不会发生互相干扰的情况。（例如下图是广播信道的通信方式，结点A、B、C、D、E
    共享广播信道，假设A要与C发生通信，B要与D发生通信，由于它们共用一条信道，如果不加控制，那么两对结点间的通信可能会因为互相干扰而失败。）
    常见的介质访问控制方法：
    静态划分信道：信道划分介质访问控制
    动态分配信道:随机访问介质访问控制和轮询访问介质访问控制
    一、信道划分介质访问控制
    将使用介质的每个设备与来自同一通信信道上的其他设备的通信隔离开来，把时域和频域资源合理地分配给网络上的设备。
    多路复用技术的概念:当传输介质的带宽超过传输单个信号所需的带宽时，人们就通过在一条介质上同时携带多个传输信号的方法来提高传输系统的利用
    率。多路复用技术把多个信号组合在一条物理信道上进行传输，使多个计算机或终端设备共享信道资源，提高了信道的利用率，实现信道划分介质访问控制。
    采用多路复用技术可把多个输入通道的信息整合到一个复用通道中，在接收端把收到的信息分离出来并传送到对应的输出通道。信道划分的实质就是通
    过分时、分频、分码等方法把原来的一条广播信道，逻辑上分为几条用于两个结点之间通信的互不干扰的子信道，实际上就是把广播信道转变为点对点信道。
    1.频分多路复用（FDM）
    频分多路复用是一种将多路基带信号调制到不同频率载波上，再叠加形成一个复合信号的多路复用技术。在物理信道的可用带宽超过单个原始信号所需
    带宽的情况下，可将该物理信道的总带宽分割成若干与传输单个信号带宽相同（或略宽〉的子信道，每个子信道传输一种信号，这就是频分多路复用。
    每个子信道分配的带宽可不相同，但它们的总和必须不超过信道的总带宽。在实际应用中，为了防止子信道之间的干扰，相邻信道之间需要加入“保护
    频带”。
    频分多路复用的优点在于充分利用了传输介质的带宽，系统效率较高；由于技术比较成熟，实现也较容易。

    2.时分多路复用（TDM）
    时分多路复用是将一条物理信道按时间分成若干时间片，轮流地分配给多个信号使用。每个时间片由复用的一个信号占用，而不像FDM那样，同一时间同
    时发送多路信号。这样，利用每个信号在时间上的交叉，就可以在一条物理信道上传输多个信号，如图3.15所示。
    □时分复用
    就某个时刻来看，时分多路复用信道上传送的仅是某一对设备之间的信号；就某段时间而言，传送的是按时间分割的多路复用信号。但由于计算机数据的突
    发性，一个用户对已经分配到的子信道的利用率一般不高。统计时分多路复用（STDM,又称异步时分多路复用）是TDM的一种改进，它采用STDM帧，
    STDM帧并不固定分配时隙，而按需动态地分配时隙，当终端有数据要传送时，才会分配到时间片，因此可以提高线路的利用率。例如，线路传输速率为
    8000b/s, 4个用户的平均速率都为2000b/s,当采用TDM方式时，每个用户的最高速率为2000b/s,而在STDM方式下，每个用户的最高速率可达8000b/s。
    30波分多路复用（WDM）
    波分多路复用即光的频分多路复用，它在一根光纤中传输多种不同波长（频率）的光信号，由于波长（频率）不同，各路光信号互不干扰，最后再用波长分
    解复用器将各路波长分解出来。由于光波处于频谱的高频段，有很高的带宽，因而可以实现多路的波分复用，如图3.16所示。
    4、码分多路复用（CDM）
    码分多路复用是采用不同的编码来区分各路原始信号的一种复用方式。与FDM和TDM不同，它既共享信道的频率，又共享时间。下面举一个直观的例子来
    理解码分复用。
    假设A站要向C站运输黄豆，B站要向C站运输绿豆，A与C、B与C之间有一条公共的道路，可以类比为广播信道，如图3.17所示。在频分复用方式下，公共道
    路被划分为两个车道，分别提供给A到C的车和B到C的车行走，两类车可以同时行走，但只分到了公共车道的一半，因此频分复用（波分复用也一样》共享
    时间而不共享空间。在时分复用方式下，先让A到C的车走一趟，再让B到C的车走一趟，两类车交替地占用公共车道。公共车道没有划分，因此两车共享了
    空间，但不共享时间。码分复用与另外两种信道划分方式大为不同，在码分复用情况下，黄豆与绿豆放在同-一-辆车上运送，到达C后，由C站负责把车上的
    黄豆和绿豆分开。因此，黄豆和绿豆的运送，在码分复用的情况下，既共享了空间，也共享了时间。